[LeetCode] 772. Basic Calculator III 基本電腦之三

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open

and closing parentheses

, the plus

or minus sign

, non-negative integers and empty spaces

The expression string contains only non-negative integers,

operators , open

and empty spaces

. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of

[-2147483648, 2147483647]

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Note: Do not use the

eval

built-in library function.

這道題是基本電腦系列的第三道，前兩道分别為 Basic Calculator 和 Basic Calculator II，差別是，第一道隻有加減法跟括号，第二道隻有加減乘除法，而這第三道既有加減乘除法又有括号運算。其實做過前兩道題的話，那麼這道題也就沒什麼問題，因為把前兩道題的解法綜合一下就是這道題的解法啦。由于此題既有括号，又有乘除法，我們知道括号是優先級最高的，但是好就好在我們可以将括号裡的内容當作一個整體調用遞歸函數來處理。而其他部分，就跟第二道一模一樣了。我們還是分情況來處理周遊，我們需要幾個變量，num 表示目前的數字，curRes 表示目前的結果，res 為最終的結果，op 為操作符号，初始化為 '+'。當遇到數字的時候，我們将 num 自乘以 10 并加上這個數字，這是由于可能遇到多位數，是以每次要乘以 10。當遇到括号的時候，這裡就有一個小 trick，由于表示可能會有括号嵌套括号，是以我們如果搜尋右括号的話，就有可能使得括号沒有正确的比對上，是以我們用一個變量 cnt，遇到左括号自增1，遇到右括号自減1，當 cnt 為0的時候，說明括号正好完全比對，這個 trick 在驗證括号是否 valid 的時候經常使用到。然後我們就是根據左右括号的位置提取出中間的子字元串調用遞歸函數，傳回值賦給 num。如果遇到符号，或者是最後一個位置的字元時，我們根據 op 的值對 num 進行分别的加減乘除的處理，結果儲存到 curRes 中。然後再次判讀如果 op 是加或減，或者是最後一個位置的字元時，将 curRes 加到結果 res 中，并且 curRes 重置為0。最後将目前字元c指派給 op（注意這裡隻有當時最後一個位置的字元時，才有可能不是運算符号，不過也不要緊了，因為周遊已經結束了），num 也要重置為0，參見代碼如下：

class Solution {
public:
    int calculate(string s) {
        int n = s.size(), num = 0, curRes = 0, res = 0;
        char op = '+';
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                int j = i, cnt = 0;
                for (; i < n; ++i) {
                    if (s[i] == '(') ++cnt;
                    if (s[i] == ')') --cnt;
                    if (cnt == 0) break;
                }
                num = calculate(s.substr(j + 1, i - j - 1));
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) {
                switch (op) {
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-' || i == n - 1) {
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            }
        }
        return res;
    }
};

Github 同步位址：

https://github.com/grandyang/leetcode/issues/772

類似題目：

Basic Calculator IV

Basic Calculator II

Basic Calculator

參考資料：

https://leetcode.com/problems/basic-calculator-iii/

https://leetcode.com/problems/basic-calculator-iii/discuss/113597/C++-recursive

https://leetcode.com/problems/basic-calculator-iii/discuss/113593/C++-Consise-Solution

https://leetcode.com/problems/basic-calculator-iii/discuss/113592/Development-of-a-generic-solution-for-the-series-of-the-calculator-problems

LeetCode All in One 題目講解彙總(持續更新中...)

喜歡請點贊，疼愛請打賞❤️~.~

微信打賞

[LeetCode] 772. Basic Calculator III 基本電腦之三

Venmo 打賞