網(wǎng)站測試有哪些主要工作市場營銷
波蘭式、逆波蘭式相關(guān)知識(shí)和題目
- 波蘭式、逆波蘭式介紹
- 常規(guī)表達(dá)式轉(zhuǎn)換成逆波蘭式
- ==編程讓常規(guī)表達(dá)式轉(zhuǎn)換成逆波蘭式==
- 逆波蘭式運(yùn)算過程
- 常規(guī)表達(dá)式轉(zhuǎn)換成波蘭式
- ==編程讓常規(guī)表達(dá)式轉(zhuǎn)換成波蘭式==
- 波蘭式運(yùn)算過程
- 150. 逆波蘭式表達(dá)式求值
- 224. 基本計(jì)算器
- 227. 基本計(jì)算器Ⅱ
- 282. 給表達(dá)式添加運(yùn)算符
波蘭式、逆波蘭式介紹
我們??吹降乃膭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添加以及添加什么,有四種選擇:
- 什么都不添加:更新之前表達(dá)式的最后一個(gè)數(shù)字num1,假設(shè)當(dāng)前數(shù)字是num2,num1=num1*10+num2,同時(shí)更新之前的表達(dá)式結(jié)果val = val - num1(舊) + num1(新)。
- 添加一個(gè)’+':更新之前表達(dá)式,加上當(dāng)前的數(shù)字num2,表達(dá)式的值val = val + num2;
- 添加一個(gè)’-':更新之前表達(dá)式,減去當(dāng)前的數(shù)字num2,表達(dá)式的值val = val - num2;
- 添加一個(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;}
};