波蘭式、逆波蘭式介紹

我們?？吹降乃膭t運(yùn)算的計(jì)算式，比如2+3*(4-9)，稱為中綴表達(dá)式，人類去計(jì)算的時(shí)候知道這些運(yùn)算符是有優(yōu)先級(jí)的：（）> */ > +-，但是讓計(jì)算機(jī)去運(yùn)算就有歧義了。上面的式子是很簡單的，實(shí)際可以遇到很多層括號(hào)，計(jì)算機(jī)不會(huì)去括號(hào)的。因此就有了波蘭式和逆波蘭式。
波蘭式和逆波蘭式里，沒有括號(hào)，計(jì)算沒有歧義。
波蘭式，也稱為前綴表達(dá)式，即運(yùn)算符在前面，數(shù)字在后面，上面的計(jì)算式轉(zhuǎn)換成波蘭式后為+2*3-49。
逆波蘭式，也稱為后綴表達(dá)式，即運(yùn)算符都在后面，數(shù)字在前面，上面的計(jì)算式轉(zhuǎn)換成逆波蘭式后為2349-*+。

常規(guī)表達(dá)式轉(zhuǎn)換成逆波蘭式

可以通過添括號(hào)、開括號(hào)把中綴表達(dá)式變成逆波蘭式，依舊以上面的式子為例子，添括號(hào)是指對應(yīng)每個(gè)運(yùn)算數(shù)和每次運(yùn)算都添加一層括號(hào)，上式添括號(hào)后變成((2) + ((3) * ((4) - (9))))。然后從最里面一層括號(hào)開始，去括號(hào)，并將運(yùn)算符放在數(shù)字后面：

• 1、((2) + ((3) * (49-)))
• 2、((2) + (349-*))
• 3、(2349-*+)
• 4、2349-*+

編程讓常規(guī)表達(dá)式轉(zhuǎn)換成逆波蘭式

如何讓計(jì)算機(jī)將中綴表達(dá)式變成逆波蘭式呢？ 轉(zhuǎn)換成逆波蘭式最重要的是運(yùn)算符的順序，需要考慮括號(hào)、優(yōu)先級(jí)、以及左右順序。轉(zhuǎn)換過程中用一個(gè)棧保存遍歷過程中遇到的運(yùn)算符。從左到右遍歷表達(dá)式的時(shí)候，遇到運(yùn)算數(shù)，直接加入到結(jié)果表達(dá)式中；遇到運(yùn)算符，需要入?；蛘叱鰲?#xff1a;

• 如果當(dāng)前運(yùn)算符是’)‘，即括號(hào)內(nèi)運(yùn)算結(jié)束了，那么一直到棧內(nèi)的’('，所有的運(yùn)算符都出棧；
• 如果當(dāng)前運(yùn)算符是’(‘，表示括號(hào)內(nèi)運(yùn)算開始，’('直接入棧；
• 如果當(dāng)前棧頂運(yùn)算符是’('，當(dāng)前運(yùn)算符直接入棧；
• 如果當(dāng)前運(yùn)算符等級(jí)高于棧頂運(yùn)算符等級(jí)，直接入棧；比如當(dāng)前是’*‘，棧頂是’+'，直接入棧；
• 如果當(dāng)前運(yùn)算符等級(jí)低于或者等于棧頂運(yùn)算符等級(jí)，就出棧，直到?？?or 棧頂運(yùn)算等級(jí)更低，當(dāng)前運(yùn)算符入棧；

遍歷完計(jì)算式后，如果棧不空將棧內(nèi)運(yùn)算符依次取出加入逆波蘭式中，依舊以上面的2+3*(4-9)為例，轉(zhuǎn)換成逆波蘭式的過程如下：

原計(jì)算式	說 明	逆波蘭式計(jì)算式	~棧~
2+3*(4-9)	2—運(yùn)算數(shù)直接加入結(jié)果中	2	空
+3*(4-9)	+—運(yùn)算符且?？?#xff0c;直接入棧	2	+
3*(4-9)	3—運(yùn)算數(shù)直接加入結(jié)果中	23	+
*(4-9)	*—運(yùn)算符且比棧頂+等級(jí)高，直接入棧	23	+*
(4-9)	(—直接入棧	23	+*(
4-9)	4—運(yùn)算數(shù)直接加入結(jié)果中	234	+*(
-9)	- —運(yùn)算符，且棧頂是(，直接入棧	234	+*(-
9)	9—運(yùn)算數(shù)直接加入結(jié)果中	2349	+*(-
)	)—運(yùn)算符，前面到(都出棧加入結(jié)果中	2349-	+*
將棧內(nèi)運(yùn)算符全都加入結(jié)果中	2349-*+	空

代碼（C++）【不確定是否正確……】：

//判斷優(yōu)先級(jí)
int operator_priority(char ch){        if (ch== '+' || ch == '-')return 1;if (ch == '*' || ch == '/')return 2;if(ch == '(')return 0;return 0;
}
//判斷是否是操作符
bool is_operator(char ch){return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')');
}//轉(zhuǎn)換成逆波蘭式 
vector<string> RPN(string s){vector<string> tokens;string operators;for(int i = 0 ; i < s.size() ; ){//操作符if(is_operator(s[i])){//如果是) 直到遇到( 操作符一直出棧if(s[i] == ')'){while(operators.back()!='('){tokens.emplace_back(string(1,operators.back()));operators.pop_back();}operators.pop_back();i++;}//操作符棧為空 或者 棧頂為( 或者 當(dāng)前為( 直接入棧else if(operators.empty() || operators.back() == '(' ||s[i] == '(')operators.push_back(s[i++]);//當(dāng)前操作符優(yōu)先級(jí)更高 直接入棧else if(operator_priority(s[i]) > operator_priority(operators.back()))operators.push_back(s[i++]);//當(dāng)前操作符優(yōu)先級(jí)更低或者一樣 前面的出棧    else{do{tokens.emplace_back(string(1,operators.back()));operators.pop_back();}while(operator_priority(s[i]) <= operator_priority(operators.back()));operators.push_back(s[i++]);}}     //操作數(shù)     else {int start = i;do{i++;}while(i<s.size() && !is_operator(s[i]));//操作數(shù)可能不止一位tokens.emplace_back(s.substr(start,i - start));}}while(!operators.empty()){tokens.emplace_back(string(1,operators.back()));operators.pop_back();            }return tokens;
}

逆波蘭式運(yùn)算過程

計(jì)算逆波蘭式的時(shí)候，從前往后遍歷式子，遇到運(yùn)算符的時(shí)候，對其前面緊跟的兩個(gè)運(yùn)算數(shù)進(jìn)行運(yùn)算：

• 2349-*+從前往后遍歷先遇到’-'，然后計(jì)算得到23(-5)*+;
• 23(-5)*+繼續(xù)往后遍歷遇到’*'，計(jì)算得到2(-15)+；
• 2(-15)+繼續(xù)往后遍歷遇到’+'，計(jì)算得到-13即為答案；

常規(guī)表達(dá)式轉(zhuǎn)換成波蘭式

可以通過添括號(hào)、開括號(hào)把中綴表達(dá)式變成波蘭式，依舊以上面的式子為例子，添括號(hào)是指對應(yīng)每個(gè)運(yùn)算數(shù)和每次運(yùn)算都添加一層括號(hào)，上式添括號(hào)后變成((2) + ((3) * ((4) - (9))))。然后從最里面一層括號(hào)開始，去括號(hào)，并將運(yùn)算符放在數(shù)字前面：

• 1、((2) + ((3) * (-49)))
• 2、((2) + (*3-49))
• 3、(+2*3-49)
• 4、+2*3-49

編程讓常規(guī)表達(dá)式轉(zhuǎn)換成波蘭式

！！！還不會(huì)！！！待解決……
或許是按照逆波蘭式的解法，只是從后向前遍歷原計(jì)算式，最后得到的結(jié)果再reverse一下（？）

波蘭式運(yùn)算過程

計(jì)算波蘭式的時(shí)候，從后往前，遇到運(yùn)算符的時(shí)候，對其后面緊跟的兩個(gè)運(yùn)算數(shù)進(jìn)行運(yùn)算：

• +2*3-49從后往前最先遇到’-'，運(yùn)算后變成+2*3(-5)
• +2*3(-5)繼續(xù)向前遍歷遇到’*'，運(yùn)算后變成+2(-15)
• +2(-15)繼續(xù)向前遍歷遇到’+'，運(yùn)算后得到-13，即為答案

150. 逆波蘭式表達(dá)式求值

題目鏈接：150. 逆波蘭式表達(dá)式求值
題目內(nèi)容：

實(shí)際就按照逆波蘭式的計(jì)算方法，遍歷逆波蘭式，遇到運(yùn)算數(shù)就放入棧，遇到運(yùn)算符就依次取棧頂元素，取兩次，得到運(yùn)算數(shù)num1和num2，做運(yùn)算后將結(jié)果壓入棧中；直到遍歷完逆波蘭式，得到的就是結(jié)果。
需要注意，num1和num2的四則運(yùn)算，加法和乘法，兩個(gè)數(shù)可以交換左右順序，但是在減法和除法中，num1 - num2 ≠ num2 - num1，需要注意第一個(gè)從棧頂取出的是num2，之后取的是num1。
代碼如下（C++）：

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> num;for(int i = 0; i < tokens.size(); i++){//運(yùn)算數(shù)直接入棧if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"){//需要將string轉(zhuǎn)換成int數(shù)字num.push(atoi(tokens[i].c_str()));}else{//注意先取的是nums2int num2 = num.top();num.pop();//之后取的是nums1int num1 = num.top();num.pop();//根據(jù)運(yùn)算符做運(yùn)算switch(tokens[i][0]){case '+':num.push(num1 + num2);break;case '-':num.push(num1 - num2);break;case '*':num.push(num1 * num2);break;case '/': num.push(num1 / num2);break;}}}//最后壓入棧的就是答案return num.top();}
};

224. 基本計(jì)算器

題目鏈接：224. 基本計(jì)算器
題目內(nèi)容：

提示里需要注意的是，這個(gè)題目的運(yùn)算只有加減，沒有乘除。在只有加減的情況下，這個(gè)題目就單純考察怎么開括號(hào)了。加法和減法優(yōu)先級(jí)是一樣的，括號(hào)對加法是沒有用的，即(2+3) + (5-2)實(shí)際（5-2)的括號(hào)不加也行——(2+3) +5 -2；但對于減號(hào)卻不行，(2+3) - (5-2)，如果要去掉括號(hào)，就變成了(2+3) -5 +2，括號(hào)前面的減號(hào)，打開括號(hào)后，括號(hào)內(nèi)+ 會(huì)變成-，-會(huì)變成+。并且這個(gè)效應(yīng)會(huì)隨著括號(hào)以及減號(hào)的累加而累加，比如-(…-(…-()…)…)這樣的三重括號(hào)，第一層括號(hào)內(nèi)符號(hào)全部要變，乘-1；第二層括號(hào)內(nèi)又要全部乘-1，由于第一層括號(hào)已經(jīng)乘了-1了，最終第二層括號(hào)內(nèi)的就負(fù)負(fù)得正；最內(nèi)層括號(hào)外面有三個(gè)-，因此最終還是會(huì)乘-1。
因此本題的重點(diǎn)在于開括號(hào)的時(shí)候，記錄括號(hào)前面是+還是-，是+正常運(yùn)算，是-就需要乘以-1。
實(shí)現(xiàn)代碼（C++）：

class Solution {
public:int calculate(string s) {int sign = 1;stack<int> ops;//記錄括號(hào)前的符號(hào)，1表示加，-1表示減ops.push(1);int ans = 0;int i = 0, n = s.size();//遍歷字符串swhile(i < n){if(s[i] == ' '){i++;}//如果是加號(hào)，緊接著的運(yùn)算數(shù)是＋還是-，需要看該層括號(hào)外對應(yīng)的符號(hào)opselse if(s[i] == '+'){sign = ops.top();i++;}//如果是減號(hào)，后面數(shù)字的運(yùn)算是+ or -，取決于括號(hào)前面的ops，且要反號(hào)else if(s[i] == '-'){sign = -ops.top();i++;}//如果是左括號(hào)，表示遇到新的一層括號(hào)，當(dāng)前的sign即為這個(gè)括號(hào)前的符號(hào)，入棧else if(s[i] == '('){ops.push(sign);i++;}//如果是右括號(hào)，表示一層括號(hào)結(jié)束，pop掉對應(yīng)的符號(hào)else if(s[i] == ')'){ops.pop();i++;}//是數(shù)字，就做相應(yīng)的運(yùn)算else{long num = 0;while(i < n && s[i] >= '0' && s[i] <= '9'){num = num*10 + s[i] - '0';i++;}ans += sign * num; //需要乘以sign，sign決定了這個(gè)數(shù)是加法還是減法}}return ans;}
};

如果題目中還有乘法除法，以及括號(hào)表示不同的優(yōu)先級(jí)，可以將表達(dá)式轉(zhuǎn)換成前綴表達(dá)式或者后綴表達(dá)式，即波蘭式或者逆波蘭式，然后開始運(yùn)算。

227. 基本計(jì)算器Ⅱ

題目鏈接：227. 基本計(jì)算器Ⅱ
題目內(nèi)容：

這個(gè)題目沒有括號(hào)！只需要考慮加減乘除的優(yōu)先級(jí)。因?yàn)槌朔ê统▋?yōu)先級(jí)更高，在整個(gè)算式中應(yīng)該先去計(jì)算乘法和除法，那我們就這么做！遍歷字符串s的時(shí)候做如下操作：

• 如果是運(yùn)算符，就記錄該運(yùn)算符【等到取到了其緊跟的數(shù)字，對其進(jìn)行相應(yīng)運(yùn)算】；
• 如果是數(shù)字，那么就找到這個(gè)數(shù)字的終點(diǎn)，得到一個(gè)數(shù)字；
• 這個(gè)數(shù)字要做何操作，取決于前面的操作符，如果是乘or除，就用前面一個(gè)數(shù)與這個(gè)數(shù)字做相應(yīng)運(yùn)算，結(jié)果保存；
• 如果是加法，直接保存這個(gè)數(shù)；如果是減法，保存這個(gè)數(shù)的負(fù)數(shù)；

因?yàn)檎麄€(gè)算式，第一個(gè)數(shù)字前如果有負(fù)號(hào)，那就保存其負(fù)數(shù)；如果第一個(gè)數(shù)是正數(shù)呢？因此我們要先給第一個(gè)數(shù)字一個(gè)初始化的操作符號(hào)’+'。 另外要注意遇到空格直接跳過。
最終將保存的數(shù)字全部都加起來即可。因?yàn)樵诒闅vs的過程中已經(jīng)先做了乘除以及減法了，最后統(tǒng)一做加法。
代碼如下（C++）：

class Solution {
public:   int calculate(string s) {int idx = 0, n = s.size();//用于存算式中的數(shù)字vector<int> nums;//num用于計(jì)算s中的每個(gè)不止一位的數(shù)字，比如321，需要先遍歷到3然后是2然后是1long num = 0;//保存每個(gè)數(shù)字前面的操作符char opt = '+';//遍歷swhile(idx < n){//如果是空格直接跳過if(s[idx] == ' '){idx++;continue;}//如果是數(shù)字if(s[idx] >= '0' && s[idx] <= '9'){//計(jì)算這個(gè)數(shù)字num = 0;do{num = num*10 + s[idx] -'0';idx++;}while(idx<n && s[idx] >= '0' && s[idx] <= '9');//根據(jù)這個(gè)數(shù)字前面的操作符來保存switch(opt){case '+': nums.emplace_back(num);break;case '-': nums.emplace_back(-num);break;case '*': nums.back() *= num;break;case '/': nums.back() /= num;break;}}//操作符else{opt = s[idx];idx++;}}num = 0;//將保存的數(shù)都加起來得到結(jié)果for(int i = 0; i < nums.size(); i++)num += nums[i];return num;}
};

282. 給表達(dá)式添加運(yùn)算符

題目鏈接：282. 給表達(dá)式添加運(yùn)算符
題目內(nèi)容：

這個(gè)題目我是完全不會(huì)做……看的題解，然后試圖理解……再自己試著寫一寫代碼和題解。
題目里說在數(shù)字之間添加運(yùn)算符，實(shí)際上可以添加也可以不添加，因此針對每兩個(gè)數(shù)字之間的位置，有4種選擇——不添加，或者添加+、-、*中的一個(gè)。此題用回溯法解題，時(shí)間復(fù)雜度是O(4^n)。
用回溯法解題的思路如下：

• 對于每兩個(gè)數(shù)字之間不添加or添加以及添加什么，有四種選擇：

1. 什么都不添加：更新之前表達(dá)式的最后一個(gè)數(shù)字num1，假設(shè)當(dāng)前數(shù)字是num2，num1=num1*10+num2，同時(shí)更新之前的表達(dá)式結(jié)果val = val - num1(舊) + num1(新)。
2. 添加一個(gè)’+'：更新之前表達(dá)式，加上當(dāng)前的數(shù)字num2，表達(dá)式的值val = val + num2；
3. 添加一個(gè)’-'：更新之前表達(dá)式，減去當(dāng)前的數(shù)字num2，表達(dá)式的值val = val - num2；
4. 添加一個(gè)’*‘：更新之前表達(dá)式，同時(shí)注意’*‘優(yōu)先級(jí)更高，表達(dá)式最后一個(gè)數(shù)num1，不管這個(gè)數(shù)之前是’+‘還是減’-‘還是乘’*'，表達(dá)式的值先減去val，再加上num1*num2；

• 進(jìn)行深度搜索的結(jié)束條件是，遍歷完字符串的時(shí)候，如果val == target就將當(dāng)前的表達(dá)式加入結(jié)果數(shù)組中；
• 由于每一步更新表達(dá)式值的時(shí)候，可能涉及到上一步表達(dá)式的最后一個(gè)數(shù)字的操作，因此在遞歸調(diào)用函數(shù)的時(shí)候需要將num1傳遞下去；表達(dá)式要一直增加，因此要傳遞表達(dá)式；表達(dá)式的值也需要更新，因此要傳遞val；添加什么操作符也需要傳遞。

代碼如下（C++）——抄的官方題解，真不會(huì)啊………………啊啊啊啊：

class Solution {
public:vector<string> addOperators(string num, int target) {int n = num.length();vector<string> ans;function<void(string&, int, long, long)> backtrack = [&](string &expr, int i, long res, long mul) {if (i == n) {if (res == target) {ans.emplace_back(expr);}return;}int signIndex = expr.size();if (i > 0) {expr.push_back(0); // 占位，下面填充符號(hào)}long val = 0;// 枚舉截取的數(shù)字長度（取多少位），注意數(shù)字可以是單個(gè) 0 但不能有前導(dǎo)零for (int j = i; j < n && (j == i || num[i] != '0'); ++j) {val = val * 10 + num[j] - '0';expr.push_back(num[j]);if (i == 0) { // 表達(dá)式開頭不能添加符號(hào)backtrack(expr, j + 1, val, val);} else { // 枚舉符號(hào)expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val);expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val);expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val);}}expr.resize(signIndex);};string expr;backtrack(expr, 0, 0, 0);return ans;}
};