（一道老坑爹的题）第三章栈作业题2-栈及其应用-计算机17级 7-1 表达式转换 （25 分）

 7-1 表达式转换 （25 分）

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。

输出格式:

在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +

 思路：mooc上的思路

从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。

1.运算数：直接输出

2.左括号：压入栈中

3.右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）

4.运算符：

若优先级大于栈顶运算符时，则把它压栈；

若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈

5.若各对象处理完毕，则把堆栈中存留的运算符一并输出

 

mooc思路补充：其实mooc上的思路完全没问题，但具体实现的过程还会有很多坑，在这里做一些补充

1.碰到数字直接输出，但是这里的数字可能是小数、负数(负号和数字是一起输出的)或带正号的数字;

小数的实现代码里有解释，仔细看应该ok

关于正负号与数字一起输出有两种特殊情况

第一种是正负号在第一位，例如：-1+2-1，此时负号要连着数字一起输出，而如果第一位是正的则不用。

第二种是左括号连着正负号，例如：1+（-2-1）或者2+(+5)-1，此时左括号后的负号也要连着输出，而左括号后的正号则不用

2.把算法代码分为两类，一类是数字类，一类是运算符类，其中关于正负号与数字一起输出我们放在数字类，这属于一种特殊情况的讨论，而其余的情况当做运算符处理即可。所以数字类包括整数，小数，以及那两种特殊情况，而运算符类则包括左括号，右括号，以及加减乘数符号。这样的话代码的逻辑会很清晰

if（）//数字类

{

}

else//运算符类

{

}

3.关于运算符的优先级，可以用map映射来表示，加减都设为1，乘除都设为2

4.一下这种代码要记得判空在前，顺序很重要

 

这是网上找的测试样例

 

话说这个题我之前是先实现堆栈再来做题的，毕竟数据结构学的就是这个嘛，但是用堆栈真的心累，卡了四天了，一直是段错误，实在是找不出来啊。。。所以这个题建议还是使用stl吧，方便太多了hh。。。当然我会把我那个全是段错误的题代码发出来，欢迎大佬们帮忙修改

先是stl写的正确的代码

#include<bits/stdc++.h>
using namespace std;
stack<char> sta;
map<char,int> ma;//


int main()
{
    ma['+'] = ma['-'] = 1;
    ma['*'] = ma['/'] = 2;
    string ss;
    cin>>ss;
    bool isfirst = true;
    for(int i = 0;ss[i]; i++)
    {
        //判断数字及特殊情况
        //判断ss为整数，为小数点，以及跟正负号与数字一起输出有关的两种特殊情况
        if((isdigit(ss[i])) || (ss[i]=='.') || ((i==0||ss[i-1]=='(') && (ss[i]=='+' || ss[i]=='-')))
        {
            if(!isfirst)//用来控制格式
            {
                cout<<" ";
            }
            if(ss[i]!='+')//负数时直接输出负号，正数则不用
            {
                cout<<ss[i];
            }
            while(ss[i+1]=='.'||isdigit(ss[i+1]))//如果是小数就继续往后读，之后自然会跳出这个循环
            {
                i++;
                cout<<ss[i];
            }
            isfirst = false;

        }
        else//为运算符时
        {
//cout<<" GG "<<i<<endl;
            if(ss[i]=='(')//左括号：压入栈中
            {
                sta.push(ss[i]);
            }
            else if(ss[i]==')')//右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）
            {
                while(!sta.empty() && sta.top()!='(')
                {
                    cout<<" "<<sta.top();
                    sta.pop();
                }
                sta.pop();
            }
            else if(sta.empty() ||(ma[ss[i]] > ma[sta.top()]))//ss[i]的优先级比栈顶元素的大
            {
                sta.push(ss[i]);
            }
            else
            {
                while(!sta.empty() && sta.top()!='(')//ss[i]的优先级比栈顶元素的小或等
                {
                    cout<<' '<<sta.top();
                    sta.pop();
                }
                sta.push(ss[i]);
            }
        }
    }
    while(!sta.empty())//最后把堆栈中存留的运算符一并输出
    {
        cout<<" "<<sta.top();//注意此时不需要用flag控制格式，因为判断数字那块一定已经有了输出
        sta.pop();
    }
    return 0;
}

然后就是用实现栈写的，答案是对的，但就是运行时他会卡一下，然后交上去一堆段错误。。。求大佬指点！！！

#include<cstdio>
#include<bits/stdc++.h>
#define STACK_INIT_SIZE 1000000
#define STACKINCREMENT 100000
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
//#define OVERFLOW   -2
using namespace std;
typedef char SElemType,Status;

map<char,int> ma;//


typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;

Status InitStack(SqStack &S)
{
    S.base = (SElemType*)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
    //if(!S.base)
    //exit(OVERFLOW);
    S.base = S.top;
    S.stacksize += STACKINCREMENT;
    return OK;
}

Status Push(SqStack &S,SElemType e)
{
    if(S.top - S.base >= S.stacksize)
    {
        S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
        //if(!S.base)
        //exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}

Status Pop(SqStack &S)
{
    if(S.top==S.base)
        return ERROR;
    return *--S.top;
    //return OK;
}

SElemType GetTop(SqStack &S)
{
    if(S.base==S.top)
        return ERROR;
    return *(S.top-1);
}

bool JudgeEmpty(SqStack &S)
{
    if(S.top == S.base)
        return true;
    else
        return false;
}

//胜利oid PrintStack(SqStack &S);

int main()
{
    SqStack S;
    ma['+'] = ma['-'] = 1;
    ma['*'] = ma['/'] = 2;
    InitStack(S);
    string ss;
    cin>>ss;
    bool isfirst = true;
    for(int i = 0; ss[i]; i++)
    {
        //判断数字及特殊情况
        //判断ss为整数，为小数点，以及跟负号有关的两种特殊情况
        if((isdigit(ss[i])) || (ss[i]=='.') || ((i==0||ss[i-1]=='(') && (ss[i]=='+' || ss[i]=='-')))
        {
            if(!isfirst)
            {
                cout<<" ";
            }
            if(ss[i]!='+')//负数时直接输出负号，正数则不用
            {
                cout<<ss[i];
            }
            while(ss[i+1]=='.'||isdigit(ss[i+1]))
            {
                i++;
                cout<<ss[i];
            }
            isfirst = false;
        }

        else//为运算符时
        {
            if(ss[i]=='(')
            {
                Push(S,ss[i]);
            }
            else if(ss[i]==')')
            {
                while(!JudgeEmpty(S)&&GetTop(S)!='(')
                {
                    cout<<" "<<GetTop(S);
                    Pop(S);
                }
                //if(!JudgeEmpty(S))
                Pop(S);
            }
            else if(ma[ss[i]] <= ma[GetTop(S)])
            {
                while(!JudgeEmpty(S)&&GetTop(S)!='(')
                {
                    cout<<" "<<GetTop(S);
                    Pop(S);
                }
                Push(S,ss[i]);
            }
            else if(JudgeEmpty(S)||(ma[ss[i]] > ma[GetTop(S)]) )//ss[i]的优先级比栈顶元素的大
            {
                Push(S,ss[i]);
            }
        }
    }
    while(!JudgeEmpty(S))
    {
        cout<<" "<<GetTop(S);
        Pop(S);
    }
}

 

题目链接：https://pintia.cn/problem-sets/434/problems/5893

希望有大佬能帮我解决这个问题，毕竟这几天一直是

。。。