基本計算器:
224. 基本計算器 - 力扣（LeetCode）

本體思路為，將中綴表達式轉為后綴表達式，通過后綴表達式進行運算。

中綴表達式:

我們日常生活中熟知的表達式如1+2-3=0 就是一個中綴表達式。

后綴表達式:
150. 逆波蘭表達式求值 - 力扣（LeetCode）

后綴表達式（Postfix Expression），也稱為逆波蘭表示法（Reverse Polish Notation, RPN），是一種數學表達式的表示方法。在這種表示法中，運算符緊跟在操作數之后，而不是像中綴表達式（如 3 + 4）那樣將運算符放在操作數中間。

中綴表達式：常規的數學表達式，如 3 + 4 * 2。

后綴表達式：運算符放在操作數之后，如 3 4 2 * +。

后綴表達式運算:

后綴表達式運算思想為，遇到操作數，入棧，遇到操作符，則彈出棧頂的兩個元素，進行操作符匹配運算，當表達式結束后，留在棧頂的操作數就是最后的值。

這里將元素彈出時候，需要進行左元素與右元素區分，因為如果是+*則左元素與右元素沒區別，但如果是-/，誰在左，誰在右，區別就很大。

中綴轉后綴:

中綴想要轉成后綴需要把握兩個思想

1. 遇到操作數載入容器
2. 遇到操作數，判斷操作數的優先級，進行入棧
   1. 如果棧里沒有操作符，則直接入棧
   2. 如果棧頂操作符優先級比當前操作符優先級低，則當前操作符入棧
   3. 如果比當前棧頂操作符優先級低或相等,這表示前面的操作符可以進行運算，彈出當前棧頂操作符，載入容器。將當前操作符繼續入棧。

如果遇到，( ?)，我們可以將它看作為一個子表達式，進行遞歸運算。

以下是代碼實現:

#include<iostream>
#include<map>
#include<vector>
#include<stack>
#include<functional>
#include<algorithm>
#include<string>
using namespace std;class Solution
{
public:void TrunSuffix(string& s, size_t& i, vector<string>& ret){stack<char> st;map<char, int> mp{ {'+',1},{'-',1} ,{'*',2} ,{'/',2} };while (i < s.size()){if (isdigit(s[i])){string num;for (; i < s.size(); i++){if (isdigit(s[i])){num += s[i];}else{break;}}ret.push_back(num);}else if (s[i] == '('){TrunSuffix(s, ++i, ret);}else if (s[i] == ')'){++i;while (!st.empty()){char ch = st.top();st.pop();ret.push_back(string(1, ch));}return;}else{if (st.empty() || mp[st.top()] < mp[s[i]]){st.push(s[i++]);}else{char ch = st.top();st.pop();ret.push_back(string(1, ch));st.push(s[i++]);}}}while (!st.empty()){char ch = st.top();st.pop();ret.push_back(string(1, ch));}}int Suffix(vector<string>& ret){map<string, function<int(int, int)>>mp ={{"+", [](int a, int b) {return a + b; }},{ "-", [](int a, int b) {return a - b; } },{ "*", [](int a, int b) {return a * b; } },{"/", [](int a, int b) {return a / b; }}};stack<int> st;for (auto& e : ret){if (mp.count(e)){int right = st.top();st.pop();int left = st.top();st.pop();int r = mp[e](left, right);st.push(r);}else{st.push(stoi(e));}}return st.top();}int calculate(string s){//1+2-(3*4)string news;for (size_t j = 0; j < s.size(); j++){if (s[j] != ' '){news += s[j];}}s.swap(news);news = "";for (size_t j = 0; j < s.size(); j++){if (s[j] == '-' && (j == 0 || (!isdigit(s[j - 1]) && s[j - 1] != ')'))){news += "0-";}else{news += s[j];}}s.swap(news);news = "";int flag = 0;for (int i = 0; i < s.size(); i++){if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')flag = 1;}if (!flag){string news;for (auto& e : s){if (isdigit(e)){news += e;}}return stoi(news);}vector<string> ret;size_t i = 0;TrunSuffix(s, i, ret);return Suffix(ret);}
};int main()
{int n=  Solution().calculate(  "(1+(4+5+2)-3)+(6+8)"   );cout << n << endl;return 0;
}

說一下我在寫這題的坑：

1. 這題力扣一開始會給出 “1 + 2 +( 4 - 5)”類似這種帶空格的表達式，所以在一開始的時候就需要先過濾一遍表達式，將刪除空格。

1. 我們還需要確認，是負數還是減號，如果是負號，妥妥的會坑。
   
   所以，我們還需要在”?- ”?加以判斷，如果-前面是操作數，則是正常-號。如果是操作符表示是一個負數，所以我們在直接添加 ”-0”
   
   添加成??0-? ?就更好的進行運算。
   這里還有一個特殊案例
   
   -號前面是 ) 而我們代碼會識別成這是一個負數，就會變成
   
   所以還需要特殊判斷，如果是 ) 則不進行添加 “0-”
   
   
2. ?力扣給的測試用例里會有(1231231)類似這種。如果不特殊判斷，則會直接取到1，及棧頂元素。所以我們在修正完字符串后進行檢查，如果沒有操作符直接進行返回。

最后，我們可能會在調試期間，進行輸出打印。所以在提交答案時候，請將輸出打印注釋，否則在最后幾個測試用例里會有非常長的表達式，會導致超出運行時間，過不了。