表达式求值

首先，后缀表达式不需要括号来确定优先级，而中缀表达式需要括号来确定优先级，如(2+1)X(3+4)这个中缀表达式如果没括号则无法求出正确的值，而对于这个中缀表达式对应的后缀表达式21+34+*则可以直接求出值来。

由后缀表达式求值

class Solution {
public:
    stack<int> stk;
    void eval(string& ch)
    {
        int a = stk.top(); stk.pop();
        int b = stk.top(); stk.pop();
        if (ch == "+")
        {
            stk.push(a + b);
        }
        else if (ch == "-")
        {
            stk.push(b - a);
        }
        else if (ch == "*")
        {
            stk.push(a * b);
        }
        else
        {
            stk.push(b / a);
        }
    }

    int evalRPN(vector<string>& tokens) {
        unordered_set<string> S{"+", "-", "*", "/"};
        for (auto& s : tokens)
        {
            if (S.count(s))
            {
                eval(s);
            }
            else
            {
                stk.push(stoi(s));
            }
        }

        return stk.top();
    }
};

中缀表达式求值

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

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

void eval()
{
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;

    for (int i = 0; i < str.size(); ++i)
    {
        char c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j++] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && pr[op.top()] >= pr[c]) eval();  //注意先判空如果操作栈不为空再进行优先级比较
            op.push(c);
        }
    }
    while (op.size()) eval();

    cout << num.top() << endl;

    return 0;
}