逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
逆波兰结构由弗里德里希·鲍尔(Friedrich L. Bauer)和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值,以利用堆栈结构和减少计算机内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、计算机学家查尔斯·汉布林(Charles Hamblin)在1960年代中期扩充[1][2]
在1960和1970年代,逆波兰记法广泛地被用于台式计算器,因此也在普通公众(工程、商业和金融领域)中使用。
算术表达式求值过程是:
• STEP 1:先将算术表达式转换成后缀表达式
• STEP 2:然后对该后缀表达式求值
下面试着从逻辑上证明以方法A最优。
1.其他想法。
使用二叉树,首先对表达式解析,一定能使叶子节点为数值而分支节点为运算符。
如果出现括号匹配可先将配对括号看作数值,加入待处理队列,依次调用主处理函数,解析括号内表达式。
方法可以实现,但是无论时间复杂度(主要是查找具体字符)
以及空间复杂度(最后每个非括号字符都将使用一个节点)都是不能与A方法相比的。
使用递归函数,当字符串增长后,算法稳定性只取决于编译器堆栈是否溢出。
使用宽度优先搜索,个人感觉比较靠近A方法,但是明显不是最优的(局限于搜索的枚举性)。
2.时间复杂度
假定最优方法时间复杂度为 O(n), A方法时间复杂度准确的说是 O(2n)~O(n)。
// 事实上我们可以让STEP 1和 STEP 2同时进行,那么A的时间复杂度已经是最优的。
3. 空间复杂度
空间复杂度不太好说,没有具体的写,大概想了一会,需要考虑自建链栈上限的问题。
4. 具体实施方法
初始化运算符栈op;
将’=’进栈;
从exp读取字符ch;
while (ch!=’\0′)
{ if (ch不为运算符)
将后续的所有数字均依次存放到postexp中;
else
switch(比较(op栈顶运算符,ch))
{
case ‘<‘: //栈顶运算符优先级低
将ch进栈; 从exp读取下字符ch; break;
case ‘=’: //只有栈顶运算符为'(‘,ch为’)’的情况
退栈; 从exp读取下字符ch; break;
case ‘>’: //栈顶运算符应先执行,所以出栈并存放到postexp中
退栈运算符并将其存放到postexp中; break;
}
}
若字符串exp扫描完毕,则将运算符栈op中’=’之前的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp;
这里要注意的是,优先级的比较问题,严蔚敏老师的书内貌似分成左右优先级,其实只有两个概念,
一个是栈内元素优先级,一个是栈外元素优先级。
运算符
=
(
+
–
*
/
)
栈内 0 1 3 3 5 5 6 栈外 0 6 2 2 4 4 1 上面的表其实不难理解,总的思路就是用优先级来默认判断进栈出栈。试几个实例就好,也可以自己推导出来。后缀表达式运算这里就不写了,稍稍动手就不难实现。