逆波兰表达式

总结了逆波兰表达式的计算方法和逆波兰表达式的生成方法

定义

zh.wikipedia.org/wiki/波兰表达式

zh.wikipedia.org/wiki/逆波兰表达式

波兰表示法（英语：Polish notation，或波兰记法）是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。如果操作符的元数（arity）是固定的，则语法上不需要括号仍然能被无歧义地解析

逆波兰表示法（英语：Reverse Polish notation，缩写RPN，或逆波兰记法、逆卢卡西维茨记法），在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法、后序表示法​^^。逆波兰记法不需要括号来标识操作符的优先级。

对于算式 1+(4-5)/7 可以生成抽象语法树

digraph G{
"+" -> 1;
"+" -> "/";
"/" -> "-";
"-" -> 4;
"-" -> 5;
"/" -> 7;
}

对语法数分别进行前序遍历，中序遍历和后序遍历可得

1. 前序遍历(根,左,右) +1/-457​ 波兰表达式，无需括号，表述无歧义
2. 中序遍历(左,根,右) 1+((4-5)/7)​ 需要根据子树添加括号才能保持正确的句法顺序
3. 后序遍历(左,右,根) 145-7/+​ 逆波兰表达式，无需括号，表述无歧义

逆波兰表达式计算时可以利用计算机的堆栈结构减少计算机内存访问

算法简介

从左向右遍历:

1. 遇到数字则入栈
2. 遇到运算符和操作符则出栈数字并求值，然后将结果再次入栈
3. 循环步骤1和步骤2直至遍历结束，栈顶就是结果数字

‍

普通表达式转逆波兰表达式

zhihu:逆波兰表达式和表达式求值/计算器算法

使用队列和堆栈配合即可完成转换

原理分析

对于表达式 1+5*4*7-7/2​ 等效于 (1+(((5*4)*7)-(7/2)))​

可以理解为每个括号为一颗子树：

• 低优先级的运算符是前面高优先级运算符的父节点，也就是划定了高优先级运算符的子树边界，
• 同优先级的则采用左结合律，即也是前面节点的父节点，所以 5/6*7​ 结构为((5/6)*7)​

其中括号特殊，右括号的优先级最低，左括号的优先级最高，但是配对后消失

算法简介

初始化一个 队列 (存储最终结果) 和 堆栈（存储中间操作数）

表达式最外层加上一对括号，对于表达式从左向右遍历

1. 如果为左括号，则加入堆栈

2. 如果为数字，则加入队列尾

3. 如果为运算符，则检查堆栈，与堆栈顶的运算符比较优先级

   1. 如果堆栈为空 或者 当前运算符的优先级更高，则直接入栈
   2. 如果当前运算符的优先级更低或相同，则将栈顶运算符出栈并加入队列尾，直到符合条件1，则将当前运算符入栈

4. 如果为右括号，则循环检查堆栈顶元素

   1. 如果不为左括号，将堆栈顶运算符出栈并加入队列尾
   2. 如果为左括号，则终止循环，并将左括号出栈丢弃

‍