中缀表达式(双栈)

中缀表达式可以看成是树的中缀遍历,我们用两个栈，一个存储运算符，一个存储运算数。

1.遍历中缀表达式

• 遇到数字,压入数字栈
• 遇到左括号,入栈
• 遇到右括号,进行运算，直到匹配到对应的左括号为止
• 遇到其他运算符，若栈顶元素的优先级高，那么一直运算，直到栈空/栈顶优先级低

2.若遍历完栈中还有运算符,一直操作到栈空为止

$ 时间复杂度O(N), 空间复杂度O(N)$

参考文献

每日一题&浙大mooc数据结构

AC代码

#include <iostream>
#include <stack>
#include <cstring>
#include <unordered_map>
using namespace std;

stack<int> num;
stack<char> op;
int n;

//运算符栈栈顶运算一下数字栈栈顶2个数
void eval(){
    auto b = num.top();num.pop();
    auto a = num.top();num.pop();
    auto c = op.top();op.pop();
    if (c == '+') num.push(a + b);
    else if (c == '-') num.push(a - b);
    else if (c == '*') num.push(a * b);
    else num.push(a / b);
}

int main(){
    string s;
    cin >> s;
    n = s.size();
    //初始化运算符的优先级
    unordered_map<char,int> map;
    map['+'] = 1;map['-'] = 1;
    map['*'] = 2;map['/'] = 2;

    //遍历表达式
    for (int i = 0 ; i < n ; i ++){
        if (isdigit(s[i])) {
            //遇到数字，压栈
            int x = 0, j = i;
            while (j < n && isdigit(s[j])) x = x * 10 + s[j ++] - '0';
            num.push(x);
            i = j - 1;
        } else if (s[i] == '('){
            //左括号，压栈
            op.push(s[i]);
        } else if (s[i] == ')'){
            //右括号,运算,直到匹配到左括号
            while (op.top() != '(') eval();
            op.pop();
        } else {
            //一般的运算符
            while (op.size() && map[op.top()] >= map[s[i]]) eval();
            op.push(s[i]);
        }
    }

    //栈还有运算
    while (op.size()) eval();

    cout << num.top() << endl;
    return 0;
}