中缀表达式求值

1、后缀表达式求值

【题目】Leetcode 150. 逆波兰表达式求值

【思路】每个运算符只与前两个元素有关，“最近相关性”，使用栈。

建立一个存放数的栈，逐一扫描后缀表达式中的元素。

• 如果遇到一个数，则将该数入栈；
• 如果遇到运算符，则取出栈顶的两个数进行计算，然后把结果入栈。

扫描完成后，栈中恰好剩下一个数，就是该后缀表达式的值。

【代码】

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> s;
        for (string &token : tokens) {
            //运算符,因为可能包含负数，所以先判断运算符
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                long long b = s.top();
                s.pop();
                long long a = s.top();
                s.pop();
                s.push(calc(a, b, token));
            } else {
                s.push(stoi(token)); //stoi：string to int
            }
        }
        return s.top();
    }

    long long calc(long long a, long long b, string op) {
        if (op == "+") return a + b;
        if (op == "-") return a - b;
        if (op == "*") return a * b;
        if (op == "/") return a / b;
        return 0;
    }
};
           

2、中缀表达式求值

【题目】

• Leetcode 224. 基本计算器
• Leetcode 227. 基本计算器 II
• Leetcode 772. 基本计算器 III

【思路】

主体思路：将中缀表达式转换为后缀表达式，然后求值。

【模板】中缀表达式转换为后缀表达式的过程：

建立一个用于存放运算符的栈，逐一扫描中缀表达式中的元素。

• 如果遇到一个数，输出该数；
• 如果遇到左括号，将左括号入栈；
• 如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后把左括号出栈；
• 如果遇到运算符，只要栈顶符号的优先级 >= 新符号，就不断取出栈顶并输出，最后把新符号入栈。优先级顺序为 乘除号 > 加减号 > 左括号

依次取出并输出栈中的所有剩余符号。

最终输出的序列就是一个与原中缀表达式等价的后缀表达式，再对后缀表达式求值。

【思考】如何辨别运算符是加减法运算还是正负号？

【回答】如果运算符表示的是正负号，则它一定出现在左括号之后，若左括号后面是正负号，则补0。

【代码】

class Solution {
public:
    //将中缀转成后缀表达式
    //【最近相关性】
    //符号和它之前的符号进行比较，比较符号的优先级，如果前面的比当前的优先级高，则需要计算；否则先暂时存起来
    int calculate(string s) {
        stack<char> ops;//建立一个存运算符的栈
        vector<string> tokens;
        long long val = 0;
        bool num_started = false; //判断一个数是否开始
        bool need_zero = true; //处理类似(-48)+48 的情况，在正负号前面补0
        //中缀表达式转后缀表达式
        for (char ch : s) {
            //parse 一个数值
            if (ch >= '0' && ch <= '9') {
                val = val * 10 + ch - '0';//字符串转成数值
                num_started = true;
                continue;
            } else if (num_started) {
                tokens.push_back(to_string(val));
                num_started = false;
                need_zero = false;
                val = 0;
            }
			//处理空格
            if (ch == ' ') continue;

             //处理运算符
             if (ch == '(') {
                 ops.push(ch);
                 need_zero = true;//左括号后需要补0
                 continue;
             }
             if (ch == ')') {
                 while (ops.top() != '(') {
                     //push back 包含一个符号的字符串
                     tokens.push_back(string(1, ops.top()));
                     ops.pop();
                 }
                 ops.pop(); //弹出左括号
                 need_zero = false; //右括号后可以直接跟符号所以不需要再添加0 
                 continue;
             }
             // 处理+-/*
             if (need_zero) tokens.push_back("0"); //处理+-/*之前先补0
             while (!ops.empty() && getRank(ops.top()) >= getRank(ch)) {
                 tokens.push_back(string(1, ops.top()));
                 ops.pop();
             }
             ops.push(ch);
             need_zero = true;
        }
        if (num_started) tokens.push_back(to_string(val));
        while (!ops.empty()) {
            tokens.push_back(string(1, ops.top()));
            ops.pop();
        }
        return evalRPN(tokens);
    }

    //获取运算符的级别
    int getRank(char ch) {
        if (ch == '+' || ch == '-') return 1;
        if (ch == '*' || ch == '/') return 2;
        return 0; //左括号
    }

    int evalRPN(vector<string>& tokens) {
        stack<long long> s;
        for (string &token : tokens) {
            //运算符,因为包含了负数，所以先判断运算符
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                long long b = s.top();
                s.pop();
                long long a = s.top();
                s.pop();
                s.push(calc(a, b, token));
            } else {
                s.push(stoi(token));
            }
        }
        return s.top();
    }

    long long calc(long long a, long long b, string op) {
        if (op == "+") return a + b;
        if (op == "-") return a - b;
        if (op == "*") return a * b;
        if (op == "/") return a / b;
        return 0;
    }
};
           

该代码可以同时解决上面的三个题目。