一、波兰表达式c
波兰表达式也叫前缀表达式，是一种不需要括号即可表示复杂运算的表达式。以波兰数学家Jan Łukasiewicz的名字命名。和我们平时所写的算术表达式中缀表达式有所不同，波兰表达式的运算符位于操作数之前。
波兰表达式的一般形式为：“运算符 操作数1 操作数2” ，例如中缀表达式(1+2）*3对应的波兰表达式为*+123。
二、波兰表达式解析逻辑运算符
对于中缀表达式中的逻辑运算符（&&,||,!），我们可以通过波兰表达式来替换掉这些运算符，即用对应的波兰表达式来表示逻辑运算符的运算关系。其中，&&对应and，||对应or，!对应not，具体可以参考下表。
逻辑运算符 中缀表达式 波兰表达式 && a && b & a b || a || b | a b ! !a ! a
三、波兰表达式代码
下面是一个简单的波兰表达式计算的Python代码示例：
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token in ["+", "-", "*", "/"]:
a = stack.pop()
b = stack.pop()
if token == "+":
stack.append(b + a)
elif token == "-":
stack.append(b - a)
elif token == "*":
stack.append(b * a)
else:
stack.append(int(b / a))
else:
stack.append(int(token))
return stack[0]
四、波兰表达式与二叉树
波兰表达式可以通过二叉树来表示，二叉树的结点表示运算符或操作数，左结点和右结点分别表示运算符或操作数的左侧和右侧。二叉树的叶结点都是操作数。比如表达式（8-3）*（2+6）的二叉树表示如下：
*
/ \
- +
/ \ / \
8 3 2 6
五、波兰表达式怎么算
计算波兰表达式通常使用栈来实现，从左到右遍历表达式，如果是一个操作数，则入栈，如果是一个运算符，则取出栈顶的两个元素进行运算，并把运算结果入栈。当表达式遍历完成后，栈中的唯一元素就是表达式的计算结果。比如计算波兰表达式（2,1,+,3,*）的结果可以按照以下步骤来实现：
1. 将2和1压入栈中； 2. 弹出2和1（1在栈顶），计算2+1，结果为3，将3压入栈中； 3. 将3和3压入栈中； 4. 弹出3和3（3在栈顶），计算3*3，结果为9，将9压入栈中； 5. 栈中的唯一元素9就是表达式的计算结果。
六、波兰表达式是什么
波兰表达式是将运算符前置的一种数学表达式，由波兰数学家Jan Łukasiewicz于1920年提出并命名。波兰表达式有着与中缀表达式类似的计算结果，但由于运算符的位置不同，波兰表达式更适用于计算机处理。
七、波兰表达式怎么写
在使用时，可以按照以下步骤将中缀表达式转换为波兰表达式：
1. 创建一个运算符栈和一个结果栈； 2. 从左到右遍历中缀表达式中的每个元素； 3. 如果遇到操作数，将其压入结果栈中； 4. 如果遇到运算符，则与运算符栈顶的元素进行比较： 4.1 如果该运算符的优先级高于运算符栈顶的元素，则将该运算符压入运算符栈中； 4.2 如果该运算符的优先级低于或等于运算符栈顶的元素，则不断弹出运算符栈顶的元素，直到遇到优先级低于该运算符的元素，然后将该运算符压入运算符栈中； 5. 如果遇到左括号，将其压入运算符栈中； 6. 如果遇到右括号，则连续弹出运算符栈顶元素并压入结果栈中，直到弹出的元素是左括号为止； 7. 遍历完成后，如果运算符栈中仍有元素，则依次弹出并压入结果栈中； 8. 将结果栈中的元素逆序输出即得到波兰表达式。
八、波兰表达式前中后的区别
波兰表达式有前缀、中缀和后缀（逆波兰）三种形式，中缀表达式是人们最为熟悉的，并且使用得也最多，但计算机计算的时候需要先转化为其他形式再进行计算。波兰表达式与中缀表达式之间的转换主要包括：
中缀表达式 -> 前缀表达式：使用不断弹出栈顶元素的方法，将中缀表达式转换为前缀表达式； 中缀表达式 -> 后缀表达式：使用不断弹出栈顶元素的方法，将中缀表达式转换为逆波兰表达式； 前缀表达式 -> 中缀表达式：使用递归的方法将前缀表达式转换为中缀表达式； 后缀表达式 -> 中缀表达式：使用递归的方法将后缀表达式转换为中缀表达式。
九、波兰表达式和逆波兰表达式定义
波兰表达式通常指前缀表达式，也称为波兰记法，是一种将运算符写在前面的算术表达式。逆波兰表达式通常指后缀表达式，也称为逆波兰记法，是一种将运算符写在后面的算术表达式。逆波兰表达式与波兰表达式类似，但运算符位于操作数之后。例如，中缀表达式 (1+2)*(3+4) 可以写成逆波兰表达式 1 2 + 3 4 + *
十、波兰表达式例题
1、LeetCode 150. Evaluate Reverse Polish Notation
给定一个代表逆波兰表达式的字符串，求表达式的值。可以假设给定的逆波兰表达式始终有效，且所有中间结果的计算值在范围 [-2^31, 2^31 - 1] 内。
示例：
输入: ["2", "1", "+", "3", "*"] 输出: 9
AC代码如下：
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token in ["+", "-", "*", "/"]:
a = stack.pop()
b = stack.pop()
if token == "+":
stack.append(b + a)
elif token == "-":
stack.append(b - a)
elif token == "*":
stack.append(b * a)
else:
stack.append(int(b / a))
else:
stack.append(int(token))
return stack[0]
2、LeetCode 224. Basic Calculator
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。示例 1：
输入：s = "1 + 1" 输出：2
AC代码如下：
class Solution:
def calculate(self, s: str) -> int:
num = 0 # 维护一个当前的数字
stack = [1] # 维护一个存放+，-号的栈，遇到左括号的时候入栈最后结果 * 对应的数字
sign = 1 # 维护当前的符号
res = 0 # 维护最终的结果
for i in range(0, len(s)):
if s[i].isdigit():
num = num * 10 + int(s[i])
elif s[i] == '+':
res += sign * num
num = 0
sign = stack[-1]
elif s[i] == '-':
res += sign * num
num = 0
sign = -1 * stack[-1]
elif s[i] == '(':
stack.append(sign)
elif s[i] == ')':
stack.pop()
else:
continue
res += sign * num
return res
3、LeetCode 439. Ternary Expression Parser
给一个字符串表示一个三元表达式，求它的计算结果。表达式由字符串组成，其中的操作符将提供为字符。条件运算符 ? 总是以双字符 ' ? ' 和 ' : ' 的形式出现在表达式中。
示例：
输入： "T?2:3" 输出： 2
AC代码如下：
class Solution:
def parseTernary(self, expression: str) -> str:
if len(expression) == 1:
return expression
i = 0
count = 0
# 用来统计？和：的数量,记录下当前的数字
for i in range(len(expression)):
if expression[i] == "?":
count += 1
elif expression[i] == ":":
count -= 1
if count == 0:
idx = i
break
return self.parseTernary(expression[2:idx+1]) if expression[0]=="T" else self.parseTernary(expression[idx+1:])
