后缀表达式-表达式求值以及转换

时间:2022-06-20 11:30:50
表达式由运算符和操作数组成,形式为中缀和后缀表现形式,中缀表达式为书写形式,后缀表达式为编译器处理的形式,后缀表达式没有括号。 举例: 中缀表达式:(a/(b-c+d))*(e-a)*c 后缀形式为:abc-d+/ea-*c* 后缀表达式和中缀表达式中的操作数的顺序一致。 后缀表达式的求值使用栈,将其从左向右入栈,将操作数入栈,遇到运算符,从栈中取出相应的操作数进行运算并将相应的结果存入栈,直到处理完表达式。 将中缀表达式处理为后缀表达式: 手动方式:对每一个运算操作,添加括号,并将每一对运算符移到有括号处,最后删除所有括号即可。 编程处理: 1、无括号形式:对中缀表达式从左向右扫描,遇到操作数即输出,遇到运算符时,对运算符进行入栈处理,运算符入栈处理的步骤为: ①栈为空,将运算符入栈,退出 ②栈不为空,且栈顶运算符的优先级低于当前入栈处理的运算符,退出 ③栈不为空,且栈顶运算符的优先级不低于当前入栈处理的运算符,将栈顶元素弹出,输出到后缀表达式中,重复入栈处理步骤、 2、有括号形式 括号会改变表达式的求值顺序,且左括号在入栈前以及入栈后的优先级不同。左括号在入栈前是一个高优先级运算符,在入栈后是一个低优先级运算符,因此,在处理有括号的中缀表达式时,需要区分运算符的栈内优先级以及引入优先级,除左括号外,其他运算符的两个优先级相同。 除常见运算符优先级(P76)外,为左括号分派优先级最高的引入优先级、最低的栈内优先级,对右括号分配次最高的栈内优先级和引入优先级,同时为中缀表达式的末尾端引入一个最低优先级,用于在处理完表达式时清空栈内的所有运算符。 运算符入栈以及出栈的步骤: ①栈为空,将运算符入栈,退出 ②栈不为空,运算符如果是右括号,弹出栈内的运算符,直到遇到左括号。 ②栈不为空,运算符不是左括号,如果栈顶运算符的栈内优先级低于当前处理运算符的引入优先级,入栈当前处理的运算符,否则,弹出栈顶的运算符,重复步骤①③。