【Acwing算法基础】 中缀 & 后缀表达式 （逆波兰表达式求值 | C++）

题目

• 核心 ： 根据操作符的优先级 判断是否要对当前的数进行操作 (判断子树是否遍历)
• 采用中序遍历 先计算 左子树 再计算右子树

//其他细节看代码
#include 
#include 
#include 
#include 
using namespace std;
stack num;
stack op;
//优先级表
unordered_map pr{ {'+', 1}, {'-', 1}, {'*',2}, {'/', 2} };

void eval() { // 操作
    int a = num.top();//第二个操作数
    num.pop(); // 左节点 
    int b = num.top();//第一个操作数
    num.pop();
    char p = op.top();//运算符
    op.pop();
    int r = 0;//结果 
    //计算结果
    if (p == '+') r = b + a;
    if (p == '-') r = b - a;
    if (p == '*') r = b * a;
    if (p == '/') r = b / a;
    num.push(r);//结果入栈
}

int main() {
    string s;//读入表达式
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) {
            int x = 0, j = i;//计算数字
            while (j < s.size() && 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() && pr[op.top()] >= pr[s[i]])//待入栈运算符优先级低，则先计算 
                eval();
            op.push(s[i]);//操作符入栈
        }
    }
    while (op.size()) eval();//剩余的进行计算
    cout << num.top() << endl;//输出结果
    return 0;
}

题目

• C++ 11 atoi()：它用于将给定的字符串值转换为整数值。 它接受包含整数(整数)的字符串，并返回其整数值。

class Solution {
public:
    bool isNumber(string& token) {
        return !(token == "+" || token == "-" || token == "*" || token == "/");
    }
    int evalRPN(vector& tokens) {
        stack stk;
        int n = tokens.size();
        for (int i = 0; i < n; i++) {
            string& token = tokens[i];
            if (isNumber(token)) {
                stk.push(atoi(token.c_str())); // 先把token转成 char 再把 char 转化为数字
            } else {
                int num2 = stk.top();
                stk.pop();
                int num1 = stk.top();
                stk.pop();
                if(token[0] == '+') {
                    stk.push(num1 + num2);
                }
                if(token[0] == '-') {
                    stk.push(num1 - num2);
                }
                if(token[0] == '/') {
                    stk.push(num1 / num2);
                }
                if(token[0] == '*') {
                    stk.push(num1 * num2);
                }
            }
        }
        return stk.top();
    }
};