【c++】逆波兰表达式求值（详解）

逆波兰表达式求值

题述：

什么叫逆波兰表达式？

其又称后缀表达式 ，而中缀表达式是操作数在两边，操作符在中间的表达式，但中缀表达式不方便机器运算的，比如4 + 13 / 5是一个中缀表达式，但机器是从左往右依次读取的，他都不考虑优先级，所以一定会出错，所以要把中缀表达式转为后缀表达式

4 + 13 / 5 转为后缀表达式-> 4 13 5 / +

后缀表达式特点：

操作数顺序不变，操作符在操作数的后边，并且按优先级排列，后缀表达式又称为逆波兰表达式

对于表达式的计算，两步走：

1、中缀表达式转为后缀表达式

2、后缀表达式的运算

而本题考察的就是第二点了

思路：

 操作数要入栈，遇到操作符要取两个数据出栈，怎么判断是不是操作符还是操作数？操作符就+ - * /，列出来即可，那取两个数据的顺序如何？栈的特性：先进后出，因为运算是从左往右算的，那么右操作数一定是后入栈的，所以先出的作为右操作数，紧接着再取出的操作数作为左操作数，运算完的结果还要入栈，因为要连续运算保存结果，每次都是在上一次的运算结果上继续运算

操作数入栈前要把字符串转换为整形，因为转换为整形才能直接运算

string有个把字符串转为整形的成员函数 stoi

代码如下（测试通过）：

//逆波兰表达式求值
class Solution {
public:
	int evalRPN(vector& tokens) {
		stack<int> st;//栈用来入操作数，故应为int，涉及字符串转换为int的操作
		for (auto& str : tokens)
		{
			//1、操作符取栈数据进行运算
			//2、操作数入栈
			if (str == "+" || str == "-" || str == "*" || str == "/")
			{
				int right = st.top();//先出栈的应该放在操作符右边
				st.pop();
				int left = st.top();
				st.pop();
			  //switch的判断条件不能是自定义类型，因为他不支持自定义类型
			  //switch (str)
			  //{
			  //case "+":
			  //}
	          //switch条件是字符可以，switch只能用内置类型做条件，自定义类型不行
				switch (str[0])
				{//str是string，str[0]是利用operator[]取对应字符，传入要么是
				//一个数，要么是一个运算符，所以访问第一个字符就取到对应string的内容了
				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(stoi(str));//是操作数就先转为整数再入栈
			}
		}
		
		return st.top();//最后栈中剩下的一个值就是表达式的结果
	}
};

 问题解释：

1、遇到操作符会遇到没操作数的情况?

遇到操作符不可能没操作数，因为后缀表达式都是操作数在前，操作符在后，要不然就不是后缀表达式了

2、代码中str[0]是什么意思？

str是string类型的，而str[0]，调用了string的operator[]，其返回字符，因为本题每个string类型的对象都是存一个字符串或一个操作数，比如"+"，"2"，而str[0]后，(假设第一个string对象存的是“+”)得到的是‘+’,也就是变成了一个字符，switch的条件起码是个内置类型才能支持，自定义类型不能支持

---

补充知识（中缀转后缀表达式）：

了解中缀转后缀的过程（要调整的就是操作符的顺序）：

1、操作数直接输出，不动

2、操作符入栈，操作符要通过比较确定计算顺序

①、栈为空，操作符入栈

②、栈不为空，操作符比栈顶的优先级高，入栈

③、栈不为空，操作符等于或低于当前栈顶操作符的优先级，则出栈顶的运算符，然后再入此时的操作符（比如栈顶为*，此时要入+，那么就先出*，然后再入+）

④、遇到)直接入栈，直到遇到操作符是(，此时会一直把栈中数据出栈直到遇到左括号(

⑤、最后栈中剩余的操作符会依次出栈

本质上其实就是看相邻运算符的优先级，优先级高的先运算，所以有第③点

了解即可，中缀表达式转为后缀表达式，一般不怎么考，但是选择题可能会出现

---