购物网站排行榜,网店网站技术方案,潍坊知名网站建设公司,个人做二次元网站怎么赚钱波兰式、逆波兰式相关知识和题目 波兰式、逆波兰式介绍常规表达式转换成逆波兰式编程让常规表达式转换成逆波兰式逆波兰式运算过程常规表达式转换成波兰式编程让常规表达式转换成波兰式波兰式运算过程 150. 逆波兰式表达式求值224. 基本计算器227. 基本计算器Ⅱ282. 给表达式添… 波兰式、逆波兰式相关知识和题目 波兰式、逆波兰式介绍常规表达式转换成逆波兰式编程让常规表达式转换成逆波兰式逆波兰式运算过程常规表达式转换成波兰式编程让常规表达式转换成波兰式波兰式运算过程 150. 逆波兰式表达式求值224. 基本计算器227. 基本计算器Ⅱ282. 给表达式添加运算符 波兰式、逆波兰式介绍
我们常看到的四则运算的计算式比如23*(4-9)称为中缀表达式人类去计算的时候知道这些运算符是有优先级的 */ -但是让计算机去运算就有歧义了。上面的式子是很简单的实际可以遇到很多层括号计算机不会去括号的。因此就有了波兰式和逆波兰式。 波兰式和逆波兰式里没有括号计算没有歧义。 波兰式也称为前缀表达式即运算符在前面数字在后面上面的计算式转换成波兰式后为2*3-49。 逆波兰式也称为后缀表达式即运算符都在后面数字在前面上面的计算式转换成逆波兰式后为2349-*。
常规表达式转换成逆波兰式
可以通过添括号、开括号把中缀表达式变成逆波兰式依旧以上面的式子为例子添括号是指对应每个运算数和每次运算都添加一层括号上式添括号后变成((2) ((3) * ((4) - (9))))。然后从最里面一层括号开始去括号并将运算符放在数字后面
1、((2) ((3) * (49-)))2、((2) (349-*))3、(2349-*)4、2349-*
编程让常规表达式转换成逆波兰式
如何让计算机将中缀表达式变成逆波兰式呢 转换成逆波兰式最重要的是运算符的顺序需要考虑括号、优先级、以及左右顺序。转换过程中用一个栈保存遍历过程中遇到的运算符。从左到右遍历表达式的时候遇到运算数直接加入到结果表达式中遇到运算符需要入栈或者出栈
如果当前运算符是’)‘即括号内运算结束了那么一直到栈内的’(所有的运算符都出栈如果当前运算符是’(‘表示括号内运算开始’(直接入栈如果当前栈顶运算符是’(当前运算符直接入栈如果当前运算符等级高于栈顶运算符等级直接入栈比如当前是’*‘栈顶是’直接入栈如果当前运算符等级低于或者等于栈顶运算符等级就出栈直到栈空 or 栈顶运算等级更低当前运算符入栈
遍历完计算式后如果栈不空将栈内运算符依次取出加入逆波兰式中依旧以上面的23*(4-9)为例转换成逆波兰式的过程如下
原计算式说 明逆波兰式计算式~栈~23*(4-9)2—运算数直接加入结果中2空3*(4-9)—运算符且栈空直接入栈23*(4-9)3—运算数直接加入结果中23*(4-9)*—运算符且比栈顶等级高直接入栈23*(4-9)(—直接入栈23*(4-9)4—运算数直接加入结果中234*(-9)- —运算符且栈顶是(直接入栈234*(-9)9—运算数直接加入结果中2349*(-))—运算符前面到(都出栈加入结果中2349-*将栈内运算符全都加入结果中2349-*空
代码C【不确定是否正确……】
//判断优先级
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 ));
}//转换成逆波兰式
vectorstring RPN(string s){vectorstring 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;}//操作符栈为空 或者 栈顶为( 或者 当前为( 直接入栈else if(operators.empty() || operators.back() ( ||s[i] ()operators.push_back(s[i]);//当前操作符优先级更高 直接入栈else if(operator_priority(s[i]) operator_priority(operators.back()))operators.push_back(s[i]);//当前操作符优先级更低或者一样 前面的出栈 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]);}} //操作数 else {int start i;do{i;}while(is.size() !is_operator(s[i]));//操作数可能不止一位tokens.emplace_back(s.substr(start,i - start));}}while(!operators.empty()){tokens.emplace_back(string(1,operators.back()));operators.pop_back(); }return tokens;
}逆波兰式运算过程
计算逆波兰式的时候从前往后遍历式子遇到运算符的时候对其前面紧跟的两个运算数进行运算
2349-*从前往后遍历先遇到’-然后计算得到23(-5)*;23(-5)*继续往后遍历遇到’*计算得到2(-15)2(-15)继续往后遍历遇到’计算得到-13即为答案
常规表达式转换成波兰式
可以通过添括号、开括号把中缀表达式变成波兰式依旧以上面的式子为例子添括号是指对应每个运算数和每次运算都添加一层括号上式添括号后变成((2) ((3) * ((4) - (9))))。然后从最里面一层括号开始去括号并将运算符放在数字前面
1、((2) ((3) * (-49)))2、((2) (*3-49))3、(2*3-49)4、2*3-49
编程让常规表达式转换成波兰式
还不会待解决…… 或许是按照逆波兰式的解法只是从后向前遍历原计算式最后得到的结果再reverse一下
波兰式运算过程
计算波兰式的时候从后往前遇到运算符的时候对其后面紧跟的两个运算数进行运算
2*3-49从后往前最先遇到’-运算后变成2*3(-5)2*3(-5)继续向前遍历遇到’*运算后变成2(-15)2(-15)继续向前遍历遇到’运算后得到-13即为答案
150. 逆波兰式表达式求值
题目链接150. 逆波兰式表达式求值 题目内容 实际就按照逆波兰式的计算方法遍历逆波兰式遇到运算数就放入栈遇到运算符就依次取栈顶元素取两次得到运算数num1和num2做运算后将结果压入栈中直到遍历完逆波兰式得到的就是结果。 需要注意num1和num2的四则运算加法和乘法两个数可以交换左右顺序但是在减法和除法中num1 - num2 ≠ num2 - num1需要注意第一个从栈顶取出的是num2之后取的是num1。 代码如下C
class Solution {
public:int evalRPN(vectorstring tokens) {stackint num;for(int i 0; i tokens.size(); i){//运算数直接入栈if(tokens[i] ! tokens[i] ! - tokens[i] ! * tokens[i] ! /){//需要将string转换成int数字num.push(atoi(tokens[i].c_str()));}else{//注意先取的是nums2int num2 num.top();num.pop();//之后取的是nums1int num1 num.top();num.pop();//根据运算符做运算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. 基本计算器
题目链接224. 基本计算器 题目内容 提示里需要注意的是这个题目的运算只有加减没有乘除。在只有加减的情况下这个题目就单纯考察怎么开括号了。加法和减法优先级是一样的括号对加法是没有用的即(23) (5-2)实际5-2)的括号不加也行——(23) 5 -2但对于减号却不行(23) - (5-2)如果要去掉括号就变成了(23) -5 2括号前面的减号打开括号后括号内 会变成--会变成。并且这个效应会随着括号以及减号的累加而累加比如-(…-(…-()…)…)这样的三重括号第一层括号内符号全部要变乘-1第二层括号内又要全部乘-1由于第一层括号已经乘了-1了最终第二层括号内的就负负得正最内层括号外面有三个-因此最终还是会乘-1。 因此本题的重点在于开括号的时候记录括号前面是还是-是正常运算是-就需要乘以-1。 实现代码C
class Solution {
public:int calculate(string s) {int sign 1;stackint ops;//记录括号前的符号1表示加-1表示减ops.push(1);int ans 0;int i 0, n s.size();//遍历字符串swhile(i n){if(s[i] ){i;}//如果是加号紧接着的运算数是还是-需要看该层括号外对应的符号opselse if(s[i] ){sign ops.top();i;}//如果是减号后面数字的运算是 or -取决于括号前面的ops且要反号else if(s[i] -){sign -ops.top();i;}//如果是左括号表示遇到新的一层括号当前的sign即为这个括号前的符号入栈else if(s[i] (){ops.push(sign);i;}//如果是右括号表示一层括号结束pop掉对应的符号else if(s[i] )){ops.pop();i;}//是数字就做相应的运算else{long num 0;while(i n s[i] 0 s[i] 9){num num*10 s[i] - 0;i;}ans sign * num; //需要乘以signsign决定了这个数是加法还是减法}}return ans;}
};如果题目中还有乘法除法以及括号表示不同的优先级可以将表达式转换成前缀表达式或者后缀表达式即波兰式或者逆波兰式然后开始运算。
227. 基本计算器Ⅱ
题目链接227. 基本计算器Ⅱ 题目内容 这个题目没有括号只需要考虑加减乘除的优先级。因为乘法和除法优先级更高在整个算式中应该先去计算乘法和除法那我们就这么做遍历字符串s的时候做如下操作
如果是运算符就记录该运算符【等到取到了其紧跟的数字对其进行相应运算】如果是数字那么就找到这个数字的终点得到一个数字这个数字要做何操作取决于前面的操作符如果是乘or除就用前面一个数与这个数字做相应运算结果保存如果是加法直接保存这个数如果是减法保存这个数的负数
因为整个算式第一个数字前如果有负号那就保存其负数如果第一个数是正数呢因此我们要先给第一个数字一个初始化的操作符号’。 另外要注意遇到空格直接跳过。 最终将保存的数字全部都加起来即可。因为在遍历s的过程中已经先做了乘除以及减法了最后统一做加法。 代码如下C
class Solution {
public: int calculate(string s) {int idx 0, n s.size();//用于存算式中的数字vectorint nums;//num用于计算s中的每个不止一位的数字比如321需要先遍历到3然后是2然后是1long num 0;//保存每个数字前面的操作符char opt ;//遍历swhile(idx n){//如果是空格直接跳过if(s[idx] ){idx;continue;}//如果是数字if(s[idx] 0 s[idx] 9){//计算这个数字num 0;do{num num*10 s[idx] -0;idx;}while(idxn s[idx] 0 s[idx] 9);//根据这个数字前面的操作符来保存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;//将保存的数都加起来得到结果for(int i 0; i nums.size(); i)num nums[i];return num;}
};282. 给表达式添加运算符
题目链接282. 给表达式添加运算符 题目内容 这个题目我是完全不会做……看的题解然后试图理解……再自己试着写一写代码和题解。 题目里说在数字之间添加运算符实际上可以添加也可以不添加因此针对每两个数字之间的位置有4种选择——不添加或者添加、-、*中的一个。此题用回溯法解题时间复杂度是O(4^n)。 用回溯法解题的思路如下
对于每两个数字之间不添加or添加以及添加什么有四种选择
什么都不添加更新之前表达式的最后一个数字num1假设当前数字是num2num1num1*10num2同时更新之前的表达式结果val val - num1(旧) num1(新)。添加一个’更新之前表达式加上当前的数字num2表达式的值val val num2添加一个’-更新之前表达式减去当前的数字num2表达式的值val val - num2添加一个’*‘更新之前表达式同时注意’*‘优先级更高表达式最后一个数num1不管这个数之前是’‘还是减’-‘还是乘’*表达式的值先减去val再加上num1*num2
进行深度搜索的结束条件是遍历完字符串的时候如果val target就将当前的表达式加入结果数组中由于每一步更新表达式值的时候可能涉及到上一步表达式的最后一个数字的操作因此在递归调用函数的时候需要将num1传递下去表达式要一直增加因此要传递表达式表达式的值也需要更新因此要传递val添加什么操作符也需要传递。
代码如下C——抄的官方题解真不会啊………………啊啊啊啊
class Solution {
public:vectorstring addOperators(string num, int target) {int n num.length();vectorstring ans;functionvoid(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); // 占位下面填充符号}long val 0;// 枚举截取的数字长度取多少位注意数字可以是单个 0 但不能有前导零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) { // 表达式开头不能添加符号backtrack(expr, j 1, val, val);} else { // 枚举符号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;}
};
