使用的数据结构:栈
转换规则:
从左到右依次遍历中缀表达式的每个数字和运算符号。
如果遍历到数字,则输出称为后缀表达式的一部分;
如果遍历到运算符号,则判断当前符号与目前在栈顶的运算符的优先级,是右括号或优先级低于栈顶的元素(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。
以中缀表达式“9+(3-1)*3+10/2”
转化为后缀表达式“9 3 1-3*+ 10 2/+”
为例说明。
- 初始化一空栈,用来对符号进出栈使用。
- 第一个字符是数字9,输出9,然后是符号“+”,进栈。
- 第三个字符是“(”,依然是符号,因其只是左括号,还未配对,故进栈。
第四个字符是数字3,输出,总表达式为9 3,接着是“-”进栈。
接下来是数字1,输出,总表达式为9 3 1,后面是符号“)”,此时,我们需要去匹配此前的“(”,所以栈顶依次出栈,并输出,直到“(”出栈为止。此时左括号上方只有“-”,因此输出“-”,总的输出表达式为9 3 1 -
接着是数字3,输出,总的表达式为9 3 1 - 3 。紧接着是符号
“*”
,因为此时的栈顶符号为“+”号,优先级低于“*”
,因此不输出,进栈。之后是符号“+”,此时当前栈顶元素比这个“+”的优先级高,因此栈中元素出栈并输出(没有比“+”号更低的优先级,所以全部出栈),总输出表达式为 9 3 1 - 3 +.然后将当前这个符号“+”进栈。也就是说,前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”,而下图中的栈底(也是栈顶)的“+”是指“9+(3-1)3+”中的最后一个“+”。
- 紧接着数字10,输出,总表达式变为9 3 1-3 * + 10。
- 最后一个数字2,输出,总的表达式为 9 3 1-3*+ 10 2
- 因已经到最后,所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1-3*+ 10 2/+