LeetCode 227. 基本計算器 II 【c++/java詳細題解】

1、題目

給你一個字串運算式 s ，請你實作一個基本計算器來計算并回傳它的值，

整數除法僅保留整數部分，

示例 1：

輸入：s = "3+2*2"
輸出：7

示例 2：

輸入：s = " 3/2 "
輸出：1

示例 3：

輸入：s = " 3+5 / 2 "
輸出：5

提示：

• 1 <= s.length <= 3 * 105
• s 由整數和算符 ('+', '-', '*', '/') 組成，中間由一些空格隔開
• s 表示一個 有效運算式
• 運算式中的所有整數都是非負整數，且在范圍 [0, 2^31 - 1] 內
• 題目資料保證答案是一個 32-bit 整數

2、思路

(堆疊,運算式求值) O ( n ) O(n) O(n)

對于運算式求值這類問題，我們維護兩個堆疊，一個num堆疊用來記錄數字，一個op堆疊用來記錄運算子，遍歷運算式，遇到運算子時進行數的相應計算，

首先我們定義一個eval()函式，用于從數字堆疊num中彈出兩個數字a和b，再從運算子堆疊op中彈出運算子號，進行計算后將結果數字加入到數字堆疊num中，

具體定義如下：

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

然后我們從前往后掃描整個運算式：

• 1、當遇到空格' '時，跳過，

• 2、當遇到數字時，則讀取一個連續的完整數字，再將其加入到數字堆疊num中，

• 3、當遇到'+'，'-'，'*'，'/' 運算子時，需要考慮優先級：

  • 如果運算子堆疊op的堆疊頂元素的優先級比當前遇到的運算子優先級高，則while回圈進行eval()操作，即將數字堆疊num堆疊頂的兩個元素取出來，然后和運算子堆疊op的堆疊頂運算子進行相應計算，并將計算結果壓回數字堆疊num中，
  • 否則，將當前運算子壓入運算子堆疊op中，

• 4、掃描完整個運算式后，如果運算子堆疊op中還存在元素，則while回圈進行eval()操作，

• 5、最侄訓傳數字堆疊num的堆疊頂元素值，

圖示程序：

細節處理：

• 1、由于運算子有優先級，所以設計一個哈希表來存盤'+'，'-'，'*'，'/' 優先級，我們將'+'和'-'設為1級優先級，將'*'和'/'設為2級優先級，
• 2、考慮到運算式s的第一個數字可能為負數，因此我們給s開頭添加一個字符0，

時間復雜度分析： 每個數字和操作進堆疊出堆疊一次，所以總的時間復雜度是 O ( n ) O(n) O(n) ，

3、c++代碼

class Solution {
public:
    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 r;
        if (c == '+') r = a + b;
        else if (c == '-') r = a - b;
        else if (c == '*') r = a * b;
        else r = a / b;
        num.push(r);
    }

    int calculate(string s) {
        s = '0' + s;  // 對開頭是負數的處理 
        unordered_map<char, int> pr; 
        pr['+'] = pr['-'] = 1, pr['*'] = pr['/'] = 2; //定義運算子的優先級
        for(int i = 0; i < s.size(); i++)
        {
            char c = s[i]; 
            if(c == ' ') continue;  //跳過空格
            if(isdigit(c))     //c是數字,讀取一個連續的數字
            {
                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  //c是運算子 
            {     //op堆疊非空并且堆疊頂運算子優先級大于等于當前運算子c的優先級，進行eval()計算
                while(op.size() && pr[op.top()] >= pr[c]) eval(); 
                op.push(c);
            }
        }
        while(op.size()) eval(); 
        return num.top();
    }
};

4、java代碼

class Solution {
    static Stack<Integer> num = new Stack<Integer>();
    static Stack<Character> op = new Stack<Character>();
    static HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    static void eval()
    {
        int b = num.pop();
        int a = num.pop();
        char c = op.pop();
        int r = 0;
        if(c == '+') r = a + b;
        else if(c == '-') r = a - b;
        else if(c == '*') r = a * b;
        else r = a / b;
        num.add(r); 
    }
    public int calculate(String s) {
        s = '0' + s; // 對開頭是負數的處理 
        map.put('+', 1);   //定義運算子的優先級
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        for(int i = 0; i < s.length();i ++)
        {
            char c = s.charAt(i);
            if(c == ' ') continue;  //跳過空格
            if(c >= '0' && c <= '9')  //c是數字,讀取一個連續的數字
            {
                int x = 0, j = i;
                while(j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9')
                {
                    x = x * 10 + s.charAt(j) - '0';
                    j ++;
                }
                i = j - 1;
                num.add(x);
            }
            else  //c是運算子 
            {     //op堆疊非空并且堆疊頂運算子優先級大于等于當前運算子c的優先級，進行eval()計算
                while(!op.isEmpty() && map.get(op.peek()) >= map.get(c)) eval();
                op.add(c); 
            }
        }
        while(!op.isEmpty()) eval();
        return num.pop();
    }
}

原題鏈接： 227. 基本計算器 II