LeetCode150 逆波兰表达式求值

题目： 给你一个字符串数组 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

思路：

逆波兰表达式相当于二叉树的后序遍历，这种表达式得到的值不受括号的影响，是非常准确的。因此可以从判断当前的字符串位上的元素是不是四则运算的符号就行，如果是则取栈顶的的元素，并将该元素弹出栈，再取下一位元素，和该符号位做四则运算，再将计算的结果压入栈中。如果不是符号位，将该元素入栈。最后返回栈顶的元素就是计算的结果。

// 输入参数为一个字符类型的 vector
double test(vector<char>& s) {// 定义一个 double 类型的栈stack<double> st;// 循环遍历输入的字符 vectorfor (int i = 0; i < s.size(); i++) {// 如果当前字符是加号、减号、乘号、除号中的一个，则将栈顶的两个数弹出做相应的运算，然后将结果压入栈中if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {double sum1 = st.top();st.pop();double sum2 = st.top();st.pop();if (s[i] == '+') st.push(sum1 + sum2);if (s[i] == '-') st.push(sum2 - sum1);if (s[i] == '*') st.push(sum1 * sum2);if (s[i] == '/') st.push(sum2 / sum1);}// 如果当前字符是数字字符，则将其转化为数字并压入栈中else {st.push(s[i] - '0');}}// 返回栈顶元素，即为计算结果return st.top();
}