逆波兰表达式

简介

介绍逆波兰表达式之前，先介绍一下运算种类。

中缀运算与后缀运算

中缀运算是一种常用的算术和逻辑公式表示方法，其中操作符位于两个运算数之间。例如，在表达式 “3 + 2” 中，加号（+）是操作符，而3和2是运算数。这种表示方法符合人类的思维结构和运算习惯，因此很容易被理解和应用。

然而，中缀表达式对计算机来说并不易于处理，尤其是当表达式包含括号时。为了使计算机能够更容易地处理这些表达式，通常会将其转换为后缀表达式（也称为逆波兰式）。

在后缀运算中，操作符被后置，如：3 2 +

中缀转后缀

我们需要借助一个栈stack。

假如1 + 2 * 3

碰到数字时，出数字；碰到运算符时，进行出入栈操作。

c步骤完成之后，回到2。

运算符的优先级是由相邻两个运算符的优先级决定的

遍历完成之后，所有操作符出栈，这就是这一多项式的逆波兰表达式

如：1 + 2 * 3 - 4 / 5

1出， +入栈， 2出， *入栈；再*出栈， +出栈（同 - 地位相等）；再 - 入栈（栈为空），再 / 入栈

最后一起出栈，结果为1 2 3 * + 4 5 / -

碰到括号该怎么办呢？

1.运算符优先级升级

2.利用！！子问题！！，借助递归，进入新的栈解决(当出现相似的问题时，可以借助子问题，递归去解决）

括号内数据遍历完成之后，所有操作符出栈，这就是括号内的逆波兰表达式，是整体表达式的一部分。

后缀转中缀

注意：是栈的第二个数据是左操作数！！！先出的是右操作数

题目

根据逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 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 <= 104
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

实现

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for (const auto& ch : tokens)   //ch是string对象{if (ch == "+"||  ch == "-"||  ch == "*"||  ch == "/"){int right = st.top();    //栈顶元素st.pop();int left = st.top();st.pop();switch (ch[0])  //得到字符（switch只允许整型）{case '+':st.push(left + right);break;case '-':st.push(left - right);break;case '*':st.push(left * right);break;case '/':st.push(left / right);break;}}else{// st.push(ch[0]);     //这是一个字符，不是数字st.push(stoi(ch));}}return st.top();}
};