中缀表达式转后缀表达式

四则表达式

• 四则表达式的计算，我们通常所见的表达式形式为中缀表达式。这是易于我们人类所理解的。机器更适合与理解后缀表达式。
• 中缀表达式**“9+（3 - 1）* 3 + 10 / 2 ”,转化为后缀表达式就是9 3 1 - 3 * + 10 2 / +**
• 中缀表达式是将以运算符为中心的计算的树形结构，用栈的来实现
  ###中缀表达式转化为后缀表达式的方法

1. 若是数字将其压入到数字栈中

2. 若是**‘（’**，压入运算符栈中

3. 若是**‘）’，计算‘（’**表达式的值

4. 其它运算符，若运算符栈顶的优先级高于其优先级，则将其弹出栈进行计算值。代码实现见eval（）

5. 其它详细内容详见大话数据结构108页
   ###代码实现

#include<bits/stdc++.h>
using namespace std;
stack<int>num;
stack<char>op;
unordered_map<char,int>pt{{'+',1},{'-',1},{'*',2},{'/',2}};
void eval()
{
    int a = num.top(); num.pop();
    int b = num.top(); num.pop();
    char x = op.top() ; op.pop();
    int y;
    if (x == '+') y = b + a;
    else if (x == '-') y = b - a;
    else if (x == '*') y = b * a;
    else y = b / a;
    num.push(y);
}
int main()
{
    string str;
    cin>>str;
    for (int i = 0 ; i < str.size() ; i ++)
    {
        if (isdigit(str[i]))
        {
            int temp = 0 , j = i;
            while (j < str.size() && isdigit(str[j]))
            {
                temp = temp*10 + str[j ++] - '0';
            }
            i = j - 1;
            num.push(temp);
        }
        else if (str[i] == '(') op.push(str[i]);
        else if (str[i] == ')')
        {
            while (op.top() != '(')eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pt[op.top()] >= pt[str[i]]) eval();
            op.push(str[i]);
        }
    }
    while (op.size())eval();
    cout<<num.top()<<endl;
    return 0;
}