表达式计算类题目

参考资料leetcode.doocs.org/lc150. 逆波兰表达式求值给你一个字符串数组tokens表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意有效的算符为、-、*和/。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是向零截断。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用32 位整数表示。示例 1输入tokens [2,1,,3,*] 输出9 解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9示例 2输入tokens [4,13,5,/,] 输出6 解释该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6示例 3输入tokens [10,6,9,3,,-11,*,/,*,17,,5,] 输出22 解释该算式转化为常见的中缀算术表达式为 ((10 * (6 / ((9 3) * -11))) 17) 5 ((10 * (6 / (12 * -11))) 17) 5 ((10 * (6 / -132)) 17) 5 ((10 * 0) 17) 5 (0 17) 5 17 5 22提示1 tokens.length 104tokens[i]是一个算符、-、*或/或是在范围[-200, 200]内的一个整数逆波兰表达式逆波兰表达式是一种后缀表达式所谓后缀就是指算符写在后面。平常使用的算式则是一种中缀表达式如( 1 2 ) * ( 3 4 )。该算式的逆波兰表达式写法为( ( 1 2 ) ( 3 4 ) * )。逆波兰表达式主要有以下两个优点去掉括号后表达式无歧义上式即便写成1 2 3 4 *也可以依据次序计算出正确结果。适合用栈操作运算遇到数字则入栈遇到算符则取出栈顶两个数字进行计算并将结果压入栈中经典单栈做法intevalRPN(vectorstringtokens){stackintnums;for(conststrings:tokens){if(s||s-||s*||s/){intbnums.top();nums.pop();intanums.top();nums.pop();if(s)nums.push(ab);elseif(s-)nums.push(a-b);elseif(s*)nums.push(a*b);elseif(s/)nums.push(a/b);}else{nums.push(stoi(s));}}returnnums.top();}227. 基本计算器 II给你一个字符串表达式s请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。你可以假设给定的表达式总是有效的。所有中间结果将在[-2^31, 2^31 - 1]的范围内。**注意**不允许使用任何将字符串作为数学表达式计算的内置函数比如eval()。示例 1输入s 32*2 输出7示例 2输入s 3/2 输出1示例 3输入s 35 / 2 输出5提示1 s.length 3 * 105s由整数和算符[, -, *, /]组成中间由一些空格隔开s表示一个有效表达式表达式中的所有整数都是非负整数且在范围[0, 231 - 1]内题目数据保证答案是一个32-bit 整数这是一个最经典的表达式计算题目不包含负数不包括括号双栈做法classSolution{public:intcalculate(string s){stackintnums;stackcharops;unordered_mapchar,intpri{{,0},{-,0},{*,1},{/,1},};functionvoid()calc[]{intbnums.top();nums.pop();intanums.top();nums.pop();intopops.top();ops.pop();switch(op){case:nums.push(ab);break;case-:nums.push(a-b);break;case*:nums.push(a*b);break;case/:nums.push(a/b);break;}};for(inti0,ns.size();in;i){if(s[i] )continue;if(isdigit(s[i])){intji;intnum0;// 注意这里数字可能越界需要加上 jn 判断while(jnisdigit(s[j])){numnum*10(s[j]-0);}nums.push(num);ij-1;}else{// 注意需要排除栈顶元素为 ( 的情况while(ops.size()ops.top()!(pri[ops.top()]pri[s[i]]){calc();}ops.push(s[i]);}}while(ops.size()){calc();}returnnums.top();}};772. 基本计算器Ⅲ实现一个基本的计算器来计算简单的表达式字符串。表达式字符串只包含非负整数算符、-、*、/左括号(和右括号)。整数除法需要向下截断。你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足[-2^31, 2^31 - 1]。**注意**你不能使用任何将字符串作为表达式求值的内置函数比如eval()。示例 1输入s 11 输出2示例 2输入s 6-4/2 输出4示例 3输入s 2*(55*2)/3(6/28) 输出21提示1 s 104s由整数、、-、*、/、(和)组成s是一个有效的表达式和 227 题的区别 在于这里可能包含括号但处理逻辑并不复杂。双栈做法classSolution{public:intcalculate(string s){stackintnums;stackcharops;unordered_mapchar,intpri{{,0},{-,0},{*,1},{/,1},};functionvoid()calc[]{intbnums.top();nums.pop();intanums.top();nums.pop();intopops.top();ops.pop();switch(op){case:nums.push(ab);break;case-:nums.push(a-b);break;case*:nums.push(a*b);break;case/:nums.push(a/b);break;}};for(inti0,ns.size();in;i){if(s[i] )continue;if(isdigit(s[i])){intji;intnum0;// 注意这里数字可能越界需要加上 jn 判断while(jnisdigit(s[j])){numnum*10(s[j]-0);}nums.push(num);ij-1;}else{if(s[i]()ops.push(s[i]);elseif(s[i])){while(ops.top()!(){calc();}ops.pop();}else{// 注意需要排除栈顶元素为 ( 的情况while(ops.size()ops.top()!(pri[ops.top()]pri[s[i]]){calc();}ops.push(s[i]);}}}while(ops.size()){calc();}returnnums.top();}};224. 基本计算器给你一个字符串表达式s请你实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数比如eval()。示例 1输入s 1 1 输出2示例 2输入s 2-1 2 输出3示例 3输入s (1(452)-3)(68) 输出23提示1 s.length 3 * 105s由数字、、-、(、)、和 组成s表示一个有效的表达式不能用作一元运算(例如1和(2 3)无效)-可以用作一元运算(即-1和-(2 3)是有效的)输入中不存在两个连续的操作符每个数字和运行的计算将适合于一个有符号的 32位 整数224 题对四则运算和括号的处理和 772/227 没啥区别虽然 224 不不需要支持乘除法但 224 中提到负数可能作为一元运算符这就要求我们对符号作为一算符的情况特殊处理因为我们的双栈数字栈和符号栈默认运算符都是二元的左右括号特殊处理。具体的对负数是一元运算符的情况我们需要将其改造为二元运算符的形式即对于-x将其改造为0 - x也就是在负号前面补一个 0 充当左运算符。双栈做法基于 772 的基础改进// 需要使用 long long不然对于 -2147483648 这个测试用例会溢出// 因为我们计算时是会把 -2147483648 表达为 0-2147483648// 具体执行代码就出现了 2147483648典型的 int 场景下负数转正数溢出问题classSolution{public:intcalculate(string s){stacklonglongnums;stackcharops;unordered_mapchar,intpri{{,0},{-,0},{*,1},{/,1},};functionvoid()calc[]{longlongbnums.top();nums.pop();longlonganums.top();nums.pop();charopops.top();ops.pop();switch(op){case:nums.push(ab);break;case-:nums.push(a-b);break;case*:nums.push(a*b);break;case/:nums.push(a/b);break;}};for(inti0,ns.size();in;i){if(s[i] )continue;// 补 0 逻辑if(s[i]-){intprevi-1;while(prev0s[prev] )prev--;// 此时负号是一元运算符if(prev0||s[prev]()nums.push(0);}if(isdigit(s[i])){intji;longlongnum0;// 注意这里数字可能越界需要加上 jn 判断while(jnisdigit(s[j])){numnum*10(s[j]-0);}nums.push(num);ij-1;}else{if(s[i]()ops.push(s[i]);elseif(s[i])){while(ops.top()!(){calc();}ops.pop();}else{// 注意需要排除栈顶元素为 ( 的情况while(ops.size()ops.top()!(pri[ops.top()]pri[s[i]]){calc();}ops.push(s[i]);}}}while(ops.size()){calc();}returnnums.top();}};