中缀表达式转后缀表达式

1. 为什么会有中缀表达式转后缀表达式

计算机中的计算器的工作原理，就是当你输入的是正常的中缀表达式，2+3*(7-4)+8/4
但是计算机是读不懂这个表达式的，因为计算机每次处理只能处理一个字符，所以，就需要把中缀表达式，换一个表达方式-> 如后缀表达式2 3 7 4 - * + 8 4 / +

计算机中：后缀表达式的运算

a b c * + d e * f + g * +

数字依次入栈
碰到符号，栈顶的出栈作为 右操作数
再次出栈 作为左操作数
结果再次入栈

2. 例题

#include
#include//万能开头 
#include
#include
#include
#include
using namespace std;
void f(string str)
{
    stack<char>s;
    map<char,int>m;
    m['+'] = m['-'] = 1;m['*'] = m['/'] = 2;m['('] = m[')'] = 3;//方便后面48行的书写 
    int i=0,j=0;
    while(i<str.length())
    {
        if(isdigit(str[i])||(i<1||str[i-1]=='(')&&(str[i]=='+'||str[i]=='-'))//判断数字和+2这种带符号数 
        {
            if(i!=0&&j!=0)
            {
                 cout<<" ";
            }
            else j++;
            if(str[i]!='+')cout<<str[i];//这一点要注意  可能是- 正号不用输出 但负号要输出   数字输出 
            while(str[i+1]=='.'||isdigit(str[i+1]))//多个数字  例如111 11.2 
            {
                i++;
                cout<<str[i];
            }
            i++;
        }       
        else
        {
            if(str[i]=='(') //考虑情况较少  先判断 
            {
                s.push(str[i]);
            }
            else if(str[i]==')') 
            {
                while(!s.empty()&&s.top()!='(') 
                {
                    cout<<" "<<s.top();
                    s.pop();
                }
                s.pop();
            }
            else
            {
                while(!s.empty()&&m[s.top()]>=m[str[i]]&&s.top()!='(')
                {
                    cout<<" "<<s.top();
                    s.pop();
                }
                s.push(str[i]);
            }
            i++;
        }
    }
    while(!s.empty())//输出全部内容 
    {
        cout<<" "<<s.top();
        s.pop();
    }
}
int main()
{
    string str;
    cin>>str;
    f(str);
    return 0;
}
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

解析答案：

1. 对题意的理解

通过对中缀表达式中的 运算符，入栈，通过判断栈顶的优先级，和即将入栈的运算符的优先级，进行比较，如果即将入栈的运算符的优先级，大于栈顶运算符的优先级，说明不需要出栈，且正常入栈。如果即将入栈的运算符的优先级，小于栈顶运算符的优先级，那么说明栈顶优先级高的运算符需要先运算完毕，后把优先级小的运算符入栈。

2. map的作用

运算符的优先级需要进行比较，那么怎么比较运算符的优先级呢？
就比如 （+) < ( * )
我们可以让 + 等于 1，而* 等于2
那么 1 < 2
所以这样的话，我们就想到了map

	map<char,int>m;
    m['+'] = m['-'] = 1;
    m['*'] = m['/'] = 2;
    m['('] = m[')'] = 3;
1
2
3
4

这样的话，我们就直接可以获取到 比如 + 所对应的优先级了
就是 m[ ‘+’ ] 这个表达式 就是 等于 1 了

3. 对数字的处理

注意以下情况：

1. 数字可能是负数（-1）正数也可能带+号
2. 数字可能还带小数（这种情况，我们考虑到了double来 接收数字，但是，我们思考一下，我们还要输出double，但是每个小数都不是固定的有效位输出，所以我们还是需要使用int输出，就是多输出一次）

4. 对运算符的处理

运算符有优先级，我们由例题的案例可以看出，当运算符从左往右遍历的时候，出现优先级比上一个优先级小的情况，那么就说明上一个运算符先运算完，然后再把当前运算符进行与下面运算符再去比较
此过程，我们就用栈来存贮运算符

3. 面试的时候，快速方法

1. 先把所有运算 用括号 括起来
2. 把运算符 移到 括号外
3. 删除括号