中缀表达式转后缀表达式详解

一、思想介绍

(1)背景

​  中缀表达式是最常用的算术表达式形式——运算符在运算数中间。但运算时需要考虑运算符优先级。

​  后缀表达式是计算机容易运算的表达式，运算符在运算数后面，从左到右进行运算,无需考虑优先级,运算呈线性结构。

1 + 2 * 3// 中缀表达式
1 2 3 * +// 后缀表达式

​  计算机直接处理中缀表达式是比较困难的，以表达式1 + 2 * 3为例：当计算机读取到1 + 2后就可以直接得出结果3了吗？答案是否定的，因为后面可能会有优先级更高的运算符。

 ​ 就拿2来说，究竟是先和左操作数计算还是先与右操作数计算？这才是解决这类问题的核心与本质。

(2)中缀表达式转后缀表达式
1.最简单的情况：

​  后缀表达式也叫逆波兰表达式，我们可以通过以下的方法将中缀表达式转化为后缀表达式（我们用一个栈来临时存储中间遇到的操作符）：

  1. 遇到操作数，直接存储/输出

  2. 遇到操作符

    • 栈为空 or 该操作符的优先级比栈顶的操作符的优先级高 → 将该操作符压栈
    • 该操作符的优先级比栈顶的操作符优先级低 or 相同 → 弹出栈顶操作符存储，并将该操作符压栈

  3. 遍历结束后将栈里的操作符依次全部弹出

    image-20220823161956060

2.分析：

​  我们以 n1 <O1> n2 <O2> n3 <O3> n4…… 为例加以说明，其中 ni 表示操作数，Oi 表示操作符。

（1）如果 O1 的优先级高于 O2，那么毫无疑问，n2 会先与左操作数运算。

（2）如果 O1 的优先级低于 O2，那么可以让 n2 与右操作数 n3 发生运算吗？答案是否定的！因为n3 能不能先与 n2 运算还取决于 O2 O3 运算符优先级的高低。但是目前我们可以确定 O2 运算符肯定在 O1 运算符前被使用。

​  能够存储这种先进后出模式的数据结构，栈自然是不二之选！！

3.问题延伸：

  1. 对于括号怎么处理?

    ​  从上面的学习中我们不难发现，先出栈的运算符一定比后出栈的运算符先运算。而括号作为优先级最高的运算符，我们如何体现出它的“优越性”呢?

    ​  其实处理的办法很简单，进入左括号后遇到的第一个运算符无脑压栈，不管优先级高低。这样就可以保证优先运算。

    ​  其实可以将括号里的式子看成一个个独立的式子，式子的结束就是遇到右括号的时候。在结束时，我们需要把栈里的操作符依次全部弹出（左括号之上的操作符）

  2. 对于负数怎么处理?

    负数会在什么情况下出现呢?

    • 表达式的开始
    • 括号的开始

    我们只需在遇到负数时首先存储一个0，这样就可以通过减法来模拟负数

(3)后缀表达式的最终求解

​  转化为后缀表达式后，我们就不需要考虑运算符优先级的高低，利用下面的方法就可以求出最终的结果：

  • 遇到操作数 → 直接入栈

  • 遇到操作符 → 取出栈顶的两个数据进行运算，将计算结果压栈

    image-20220823160713712

（注意：转换过程中操作数的相对位置始终没有发生改变，所以栈最顶上的是右操作数，它下面的才是左操作数）

(4)参考代码

【作用】：将中缀表达式转后缀，并计算出最终的结果

#include <stack>
#include <string>
#include <cctype>
#include <iostream>
#define priority(c)  (c == '*' || c == '/')? (1) : (0)
//[解释]：宏定义一个优先级比较函数
//[注意]：为了避免宏定义一些意向不到的错误，建议多加括号
using namespace std;

class calc
{
public:
	 // 例：s = “1 + 6 / 3”
    int eval(const string& s)
	{
		int sz = s.size();
		if (s[0] == '-') //[解释]：对负数的处理，通过减法来模拟负数
			num.push(0);

		for (int i = 0; i < sz; i++)
		{
			if (s[i] == ' ')
				continue;
			else if (isdigit(s[i])) //[作用]：字符串转数字的操作
			{
				int n = s[i] - '0';
				while (i + 1 < sz && isdigit(s[i + 1]))
					n = n * 10 + (s[++i] - '0'); 
                //[注意]：括号不能少，否则有可能溢出
				num.push(n);
			}
			else if (s[i] == '(')
			{
				op.push('(');
				flag = true;//[解释]：标记进入左括号，用于无脑压栈 
				if (s[i + 1] == '-')
					num.push(0);
			}
			else if (s[i] == ')')
			{
				flag = false;
                // [注意]：在遇到括号里第一个运算符后，flag才会置为
                // false,但遇到括号里无运算符的情况就可能会出错，所
                // 以加个双保险
				char _operator = op.top();
				while (_operator != '(')
				{
                   	// [解释]：弹出运算符进行运算的过程
					count_push(_operator);
					op.pop();
					_operator = op.top();
				}
				op.pop();  // 把'('弹出来
			}
			else
			{
				if (op.empty() || flag)
				{
					op.push(s[i]);
					flag = false;
				}
				else 
				{
					char _operator = op.top();
					if (priority(_operator) >= priority(s[i]))
					{
						count_push(_operator);
						op.pop();
					}
					op.push(s[i]);
				}
			}
		}
		while (!op.empty()) //[解释]：遍历结束后将栈里的操作符依次全部弹出
		{
			count_push(op.top());
			op.pop();
		}
		return num.top();
	}
    
    //[作用]：进行栈顶两个数据的运算并压入栈中 
	void count_push(char _operator)
	{
		int tmp = 0;
		int right = num.top();
		num.pop();
		int left = num.top();
		num.pop();
		switch (_operator)
		{
		case '+':
			tmp = left + right;
			break;
		case '-':
			tmp = left - right;
			break;
		case '*':
			tmp = left * right;
			break;
		case '/':
			tmp = left / right;
			break;
		}
		num.push(tmp);
	}

	
private:
	bool flag = false;   //[作用]：用来标记是否进入左括号
	stack<int> num;	     //[作用]：存储数据的栈
	stack<char> op;      //[作用]：存储运算符的栈
};
(5)小试牛刀

150. 逆波兰表达式求值

224. 基本计算器