a017. 五則運算

思路

無括號情況

先不去考慮有括號的情況，假設當前運算式是7 + 10 + 14 * 4 - 8 / 7 * 42。
建立兩個stack，一個nums計入數字，一個oper計入運算符號。

1. 一開始遇到數字 $7$ 、 $+$ 、 $10$ 、 $+$ 、 $14$ 、 $*$
   • nums = [7, 10, 14]
   • oper = [+, +, *]
2. 這時棧頂符號是 $*$ ，因為先乘除後加減，下個數字 $4$ 跟棧頂數字 $14$ 相乘後，再放到棧中。並繼續操作
   • nums = [7, 10, 56, 8]
   • oper = [+, +, -, /]
3. 棧頂符號是 $/$ ，同樣的道理，下個數字 $5$ 跟棧頂數字 $8$ 相除。
   • nums = [7, 10, 56, 1.14]
   • oper = [+, +, -, *]
4. 棧頂符號 $*$ ，下個數字 $42$ 跟棧頂數字 $1.14$ 相乘。
   • nums = [7, 10, 56, 48]
   • oper = [+, +, -]
5. 讀完運算式，現在需要從左到右計算，否則在遇到1-1+1的情況，先結合右邊的做法會出錯。
   • return 7 + 10 + 56 - 48

由於除法會將小數位砍掉，最後程式輸出31。

有括號情況

如在運算式當中加入了括號，比如7 + (10 + (14 * 4 - 8) / 7) * 42（空格只是方便看，實際上相連）
我們能用遞迴的方式，將有括號情況簡化成沒有括號的情況。
定義dfs(i)代表從位置 $i$ 為起點，計算運算式的結果。

1. dfs(0)，一開始加入數字 $7$ 與 $+$
   • nums = [7]
   • oper = [+]
2. 遇到左括號，遞迴呼叫dfs(3)，在dfs(3)當中
   • nums = [10]
   • oper = [+]
   1. 遇到左括號，遞迴呼叫dfs(8)，計算14 * 4 - 8
   • 遇到右括號，代表遞迴結束，回傳計算結果48
   • 為了讓dfs(3)知道return時計算到哪，用變數where紀錄計算位置。where = 13（括號位置） 根據where得知還沒計算到底，從where繼續往下走，直到遇到右括號或是結尾。

• nums = [10, 48, 7]$\to$[10, 6.85]$\to$[16.85]
• oper = [+, /]$\to$[+]$\to$[] 回傳16.85，此時where = 16。

3. dfs(0)收到遞迴呼叫結果。

• nums = [7, 16.85]
• oper = [+] 根據where得知還沒計算到底，從where繼續往下走，直到遇到右括號或是結尾。
• nums = [7, 16.85, 42]
• oper = [+, *] 計算最後結果，得到714.7。

程式碼

遞迴

#include <iostream>
#include <sstream>
#include <stack>
#include <vector>
using namespace std;
int where;
void push(vector<int>& nums, vector<char>& oper, int cur, char op) {
    int n = nums.size();
    if(n == 0 || oper.back() == '+' || oper.back() == '-') {
        nums.push_back(cur);
        oper.push_back(op);
    }
    else { // * / % 
        if(oper.back() == '*') {
            nums.back() *= cur;
        }
        else if(oper.back() == '/') {
            nums.back() /= cur;
        }
        else { // % 
            nums.back() %= cur;
        }
        oper.back() = op;
    }
}
int dfs(string& s, int i) {
    vector<int> nums;
    vector<char> oper;
    int cur = 0;
    while(i < s.length() && s[i] != ')') {
        if(isdigit(s[i])) {
            cur = cur * 10 + (s[i++] - '0');
        }
        else if(s[i] != '(') { // + - * / %
            push(nums, oper, cur, s[i++]);
            cur = 0;
        }
        else { // (
            cur = dfs(s, i + 1);
            i = where + 1;
        }
    }
    push(nums, oper, cur, '+'); // + 號非必要，只是為了呼叫函數。
    where = i;
    int res = nums[0];
    for(int i = 1; i < nums.size(); ++i) {
        res += oper[i - 1] == '+' ? nums[i] : -nums[i];
    }
    return res;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    while(getline(cin, line)) {
        stringstream ss(line);
        string temp, s;
        while(ss >> temp) {
            s += temp;
        }
        if(!s.empty()) {
            cout << dfs(s, 0) << "\n";
        }
    }
}

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$