题目：

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

1
2 3 7 4 - * + 8 4 / +

思路

将中缀表达式转化为后缀表达式的方法就是从头到尾去遍历中缀表达式，利用栈来存运算符，看到数字相关的字符就输出，当遇到运算符（包括括号）时，我们要去判断该运算符与栈顶运算符优先级谁大谁小，若栈顶的大，那么栈顶的运算符可以被输出，但要是该运算符的优先级更大，我们便不能着急的输，因为我们还不知道后面有没有比它更高优先级的运算符，只能将其压入堆栈。
需要注意碰到括号的情况，当碰到的是左括号，我们是将其当作高优先级的运算符直接压入栈中，而碰到右括号时，我们应将栈顶的运算符输出，知道栈顶为左括号（括号里先算）或者栈空为止。
对于这道题还有一个更恶心的点，那就是数字可能为小数或者负数，所有我们再处理数字的时候也应将小数点和负号当作运算数来考虑，但由于本题不要求求出结果，所以我们只需原样入栈出栈输出即可。
代码如下：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//实现1
#include <bits/stdc++.h>

using namespace std;

int main()
{
    string str;
    cin>>str;
    stack<char> s;
    map<char,int> m;//保存符号的优先级便于后期判断
    m['+']=m['-']=1;m['*']=m['/']=2;//优先级从小到大依次为1，2
    int flag=1;
    for(int i=0;i<str.length();i++)
    {
        //搞清楚什么算是数字：因为这里的数可能有正有负，还带小数点，所有我们应该把这些满足条件的正负号和小数点
        //也看作数字输出，而正负号的输出条件为在它前面为左括号或者没有东西
        if((i<1||!isdigit(str[i-1])&&str[i-1]=='(')&&(str[i]=='+'||str[i]=='-')||isdigit(str[i]))//非运算符
        {
            if(flag) flag=0;
            else putchar(' ');
            if(str[i]!='+') cout<<str[i];
            while(str[i+1]=='.'||isdigit(str[i+1]))//循环输出可能出现的后面的小数部分
            {
                cout<<str[++i];
            }
        }
        else//运算符
        {
            if(str[i]=='(') s.push(str[i]);//当前字符为左括号直接入栈
            else if(str[i]==')')//如果当前字符是右括号
            {
                while(!s.empty()&&s.top()!='(')//输出栈顶运算符直到碰到左括号
                {
                    printf(" %c",s.top());
                    s.pop();
                }
                s.pop();
            }
            else//否则当前运算符不是右括号
            {
                while(!s.empty()&&s.top()!='('&&m[s.top()]>=m[str[i]])//当栈运算符优先级高于当前字符时，输出栈顶运算符
                {
                    printf(" %c",s.top());
                    s.pop();
                }
                s.push(str[i]);//将当前字符入栈
            }
        }
    }
    while(!s.empty())//输出剩余运算符
    {
        printf(" %c",s.top());
        s.pop();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//实现2
#include <bits/stdc++.h>

using namespace std;

int main()
{
    string str;
    cin>>str;
    stack<char> s;//运算符栈
    int flag=0;
    for(int i=0; i<str.length(); i++)//从左往右顺序遍历中缀表达式
    {
        if((str[i]=='+'||str[i]=='-')&&(!i||str[i-1]=='(')||isdigit(str[i]))//碰到如果当前字符是位于表达式开头或'('之后的正负号or是数字则按各自规则直接输出
        {
            if(flag) putchar(' ');
            if(str[i]!='+')//不需要输出正号
            {
                cout<<str[i];
                flag=1;
            }
            while(str[i+1]=='.'||isdigit(str[i+1]))//输出完当前字符后往后看是否为小数点或者数字，如果是则一直输出到不是为止
            {
                cout<<str[++i];
                flag=1;
            }
        }
        else//如果当前字符是运算符
        {
            if(str[i]==')')//如果当前字符是')'，则输出运算符栈里头的运算符直到遇到左括号为止
            {
                while(!s.empty()&&s.top()!='(')
                {
                    if(flag) putchar(' ');
                    cout<<s.top();
                    flag=1;
                    s.pop();
                }
                if(!s.empty()) s.pop();//将左括号不输出弹出栈
            }
            else//如果当前字符不是')'，则当栈顶运算符优先级高于当前字符的运算符优先级时输出栈顶的运算符，直到不满足上述条件
            {
                if(s.empty())//特殊情况，栈是空的，没的输出，直接将当前字符入栈，然后进入下一次循环
                {
                    s.push(str[i]);
                    continue;
                }
                while(!s.empty()&&s.top()!='(')//当栈不空并且栈顶不是'('时
                {
                    if(str[i]=='('||((str[i]=='*')||str[i]=='/')&&(s.top()=='+'||s.top()=='-'))//不满足输出条件直接break跳出
                    {
                        break;
                    }
                    if(flag) putchar(' ');
                    cout<<s.top();
                    flag=1;
                    s.pop();
                }
                s.push(str[i]);//输出完栈中该输出的以后将当前字符入栈
            }
        }
    }
    while(!s.empty())//最后处理剩下在栈里头的运算符
    {
        if(flag) putchar(' ');
        cout<<s.top();
        flag=1;
        s.pop();
    }
}