---

題目描述

使用stack處理括號化的表達式。當你看到一個左括號，將其記錄下來。當你在一個左括號之后看到一個右括號，從stack中pop對象，直至遇到左括號，將左括號也一起彈出棧。然后將一個值（括號內的運算結果）push到棧中，表示一個括號化的（子）表達式已經處理完畢，被其運算結果所替代。

---

思路

使用getline()存儲輸入的字符串

是為了避免cin在提取字符串時遇到空格會終止讀取的問題。例如：

// 當輸入1 *2時
cin >> s; // s為1
getline(cin, s); // s為1 *2

邊讀取邊壓棧

創建兩個棧：

• 一個用來存運算符
• 一個用來存操作數
  當遇到 “)” 時，彈出運算符棧中的運算符、和對應的操作數棧中的操作數并進行計算直到遇到 “(” ，完成后將這期間的運算結果壓入操作數棧。例如：
  
  處理 “ (，+，) ” 時，將1，2作為操作數從nums棧中彈出，將處理結果3壓入nums棧中，當然， “ (，+，) ” 三個運算符全部彈出symbol棧。之后：
  
  遇到右括號時，將乘號、左括號彈出棧，在這過程中將3、4作為操作數彈出nums棧進行運算，之后，將運算結果壓入nums棧。

當處理完全部括號后，將symbol棧中的運算符清空——也就是將對應的運算都進行計算，（在此過程中，減法和除法要注意操作數的先后問題）：

當symbol棧中為空時，nums棧中僅有一個元素，也就是最終的計算結果。

---

完整代碼

#include <iostream>
#include <stack>
#include <string>using namespace std;void resolve(stack<double>& s1, stack<char>& s2){while((!s2.empty()) && (s2.top() != '(')){char temp = s2.top();s2.pop();double num1 = s1.top(); //second//cout << "num1: " << num1 << endl;s1.pop();double num2 = s1.top(); //first//cout << "num2: " << num2 << endl;s1.pop();if(temp == '*'){s1.push(num1*num2);//cout << "*" << endl;}if(temp == '/'){s1.push(num2/num1); // 注意操作數的順序//cout << "/" << endl;}if(temp == '+'){s1.push(num1+num2);//cout << "+" << endl;}if(temp == '-'){ // 注意操作數的順序s1.push(num2-num1);//cout << "-" << endl;}}if(!s2.empty()){ // 當symbol棧不為空的時候if(s2.top() == '('){ // 遇見左括號也會跳出上述循環    s2.pop();          // 因此無法執行while中的pop}                    // 程序會一直卡在左括號的位置}                      // 所以在這里補上pop避免上述問題}double calculate(string& s) {if(s.empty()){return 0;}stack<double> nums;stack<char> symbol;double num = 0;string temp = ""; // 存儲連續數值字符for(size_t i = 0; i < s.size(); i++){if((s[i] >= '0' && s[i] <= '9') || s[i] == '.'){ // 數字temp += s[i]; // 連續數值字符}if(((s[i]<'0'||s[i]>'9')&&s[i]!=' ') || i==s.size()-1){ // 運算符if(!temp.empty()){num = stod(temp); // num存儲連續數值字符的終值nums.push(num);}if(s[i] == ')'){resolve(nums, symbol);}else{switch (s[i]) {case '(':case '+':case '-':case '*':case '/':symbol.push(s[i]); // 上述五種運算符直接壓棧}}num = 0;temp.clear(); // 清空temp以便存儲下一個連續數值字符}}resolve(nums, symbol);return nums.top();
}bool pankong(string& str){ // 判斷左右括號是否數量一致int left = 0;int right = 0;for(auto beg = str.begin(); beg != str.end(); beg++){switch (*beg) {case ')': right++; break;case '(': left++; break;}}if(left != right){cout << "左右括號數量不對等" << endl;return false;}else{return true;}
}int main()
{string str; // 表達式double over; // 最終值//cin >> str;getline(cin,str);if(!pankong(str)){ // 判斷左右括號數量是否一致return -1;}over = calculate(str);cout << "over: " << over << endl;return 0;
}