表达式求值

表达式求值要解决的问题一般是输入一个字符串表示的表达式，要求输出它的值。

我们要知道：算术表达式分为三种，分别是前缀表达式、中缀表达式、后缀表达式。

其中，中缀表达式是我们日常生活中最常用的表达式；后缀表达式是计算机最容易理解的表达式。

为什么说后缀表达式最容易被计算机理解呢？因为后缀表达式不需要括号表示，它的运算顺序是唯一确定的。举个例子：在后缀表达式中，首先计算（使用最后一个运算符，即栈顶运算符），然后计算 6-1=5。可以看到：对于一个后缀表达式，只需要 维护一个数字栈，每次遇到一个运算符，就取出两个栈顶元素，将运算结果重新压入栈中。最后，栈中唯一一个元素就是该后缀表达式的运算结果时间复杂度O(n) 。

经典题型

🕢

224. 基本计算器

227

150

中缀转后缀

所以说，对于普通中缀表达式的计算，我们可以将其转化为后缀表达式再进行计算。转换方法也十分简单。只要建立一个用于存放运算符的栈，扫描该中缀表达式：

如果遇到数字，直接将该数字输出到后缀表达式（以下部分用「输出」表示输出到后缀表达式）；

如果遇到左括号，入栈；

如果遇到右括号，不断输出栈顶元素到输出，直至遇到左括号（左括号出栈，但不输出）；

如果遇到其他运算符，不断去除所有运算优先级大于等于当前运算符的运算符，输出。最后，新的符号入栈；

把栈中剩下的符号依次输出，表达式转换结束。

中缀转后缀代码如下：


    def middle2behind(self, s: str) -> int:

        # 运算符优先级
        prec = {}
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1
				
				# 存放后缀表达式结果
        res = []
				# 辅助栈
        stack = []
				
        i = 0
        while i < len(s):
            # 数字 直接 接到后缀表达式上
            if s[i] == " ":
                i += 1
                
            elif s[i].isdigit():
                temp = ""
                while i < len(s) and s[i].isdigit():
                    temp += s[i]
                    i += 1
                res.append(temp)

            # 左括号直接入栈
            elif s[i] == "(":
                stack.append(s[i])
                i += 1

            # 右括号，开始弹栈，直达遇到左括号 左括号出栈 但不输出
            elif s[i] == ")":
                while stack and stack[-1] != "(":
                    res.append(stack.pop())
                stack.pop() # 左括号出战， 但是不输出
                i += 1

            # 遇到运算符
            elif s[i] in ["+", "-", "*", "/"]:
                #  对 "-2 + 2" 或者 "1-(-2)" 进行特殊处理
                if s[i] == "-" and (i == 0 or s[i-1] == "(" ):
                    res.append('0')
                # 只要栈顶符号不低于当前符号，就一直输出。最后把当前符号入栈
                while stack and prec[stack[-1]] >= prec[s[i]]:
                    res.append(stack.pop())
                stack.append(s[i])
                i += 1
        
        # 最后把栈里面的元素均 放到后缀表达式后面
        while stack:
            res.append(stack.pop())

后缀表达式计算

后缀表达式格式为数组格式。

计算如下：


def calculate(res)
		# res 为后缀表达式		
		stack = []
		for char in res:
			  if char.isdigit():
			      stack.append(int(char))
			   else:
			       x = stack.pop()
			       y = stack.pop() 
			       if char == "+":
			           stack.append(x + y)
			       elif char == "-":
			           stack.append(y-x)
			       elif char == "*":
		             stack.append(y*x)
			       elif char == "/":
			           stack.append(x/y)
		return stack.pop()