中綴表達式求值

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;
    }
};
           

該代碼可以同時解決上面的三個題目。