app制作网站收费吗,wordpress 相关插件,为什么别的电脑能打开的网站我的电脑打不开,域名怎么创建网站吗题目描述
给你一个字符串数组 tokens #xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意#xff1a;有效的算符为 、-、* 和 / 。
每个操作数#xff08;运算对象#xff09;都可以是一个整数或者另一个表达式…题目描述
给你一个字符串数组 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) 517 522思路 定义一个栈用来存放操作数。 遍历 tokens对于每一个元素检查它是否为操作符。 如果是操作符从栈中弹出两个元素执行对应操作然后将结果压入栈。如果是操作数直接将其转换为整数并压入栈。 返回栈顶元素遍历完成后栈顶元素就是表达式的结果。
这种方法的时间复杂度为 O(n)其中 n 是 tokens 数组的长度因为每个元素只被处理一次。空间复杂度主要是用于存储操作数的栈的空间最坏情况下也是 O(n)。
ps在做加减乘除的时候是num2 和 num1做加减乘除而不是num1 和 num2因为在逆波兰表示法后缀表达式中操作数的顺序与它们在表达式中的出现顺序一致。所以当从栈中弹出两个元素来应用一个操作符时先弹出的是右操作数而后弹出的最近压入的是左操作数。
完整代码
// 逆波兰表达式求值 即 后缀表达式 左右中
#includeiostream
#includevector
#includestring
#includestackclass Solution {
public:int evalRPN(std::vectorstd::string tokens) {std::stacklong long st;for(int i 0; i tokens.size(); i){if(tokens[i] || tokens[i] - || tokens[i] * || tokens[i] /){long long num1 st.top();st.pop();long long num2 st.top();st.pop();if (tokens[i] ) st.push(num2 num1);if (tokens[i] -) st.push(num2 - num1);if (tokens[i] *) st.push(num2 * num1);if (tokens[i] /) st.push(num2 / num1);}else{st.push(std::stoi(tokens[i])); // 将字符串转换为整数并压入栈中}}int result st.top();st.pop();return result;}
};int main()
{Solution s;std::vectorstd::string tokens {10,6,9,3,,-11,*,/,*,17,,5,};std::cout s.evalRPN(tokens) std::endl;return 0;
}
}
