首页 > 代码库 > “中序表达式”转换为“前序表达式”、“后序表达式”
“中序表达式”转换为“前序表达式”、“后序表达式”
首先看下面所示表格:
中序表达式 | 2*3/(2-1)+3*(4-1) |
前序表达式 | +/*23-21*3-41 |
后序表达式 | 23*21-/341-*+ |
中序表达式对我们而言是很直观的(我们平时接触的就是这个),但计算机处理起来比较麻烦(括号、优先级之类的),前序和后序表达式中没有括号,而且在计算中只需单向扫描,不需要考虑运算符的优先级。
以前序表达式“+/*23-21*3-41”为例,从右往左,先取出两个操作数“1”、“4”和一个运算符“-”,计算“4-1”,将结果3回填到字符串中,现在字符串变为“+/*23-21*33”。
再从右至左取两个数“3”、“3”和“*”,计算“3*3”,将结果“9”回填到字符串,得“+/*23-219’”,
再取数,连续取出“9”、“1”、“2”,直到取出一个运算符“-”,将与运算符最近的两个操作数进行计算,即“2-1”得“1”,回填字符串中,现在为“+/*239”
重复上述步骤,取出“2*3”=6,回填字符串得到“+/619”,
再取“6/1”=6,得到“+69”,
再取“6+9”=15。运算完毕。
即从右至左取数,直到取出一个运算符,将刚取出的紧挨着运算符的两个操作数按运算符进行计算,结果回填至运算符。重复该步骤,直到最后只剩下一个字符串则剩下的字符串即为结果。
后序表达式的字符串扫描方式正好和前序相反,是从左往右扫描,规则类似。
1、反转输入字符串,如“2*3/(2-1)+3*(4-1)” 反转后为“ )1-4(*3+)1-2(/3*2”,
2、从字符串中取出下一个字符
2.1.如果是操作数,则直接输出
2.2.如果是“)”,压入栈中
2.3.如果是运算符但不是“(”,“)”,则不断循环进行以下处理
2.3.1.如果栈为空,则此运算符进栈,结束此步骤
2.3.2.如果栈顶是“)”,则此运算符进栈,结束此步骤
2.3.2.如果此运算符与栈顶优先级相同或者更高,此运算符进栈,结束此步骤
2.3.4.否则,运算符连续出栈,直到满足上述三个条件之一,然后此运算符进栈
2.4、如果是“(”,则运算符连续出栈,直到遇见“)”为止,将“)”出栈且丢弃之
3、如果还有更多的字符串,则转到第2步
4、不在有未处理的字符串了,输出栈中剩余元素
5、再次反转字符串得到最终结果
我第一次看到这个的时候就没看懂是什么意思,在网上查了点,又瞪了它好久才明白了,就以“2*3/(2-1)+3*(4-1),”为例做以下说明:
2*3/(2-1)+3*(4-1),反转得“ )1-4(*3+)1-2(/3*2 ”;
取第一个字符串为“)”,入栈(此时栈中为“)”);
取下一个“1”,是操作数,直接输出(目前输出“1”);
取下一个“-”,既不是“)”,也不是“(”,则转到2.3,此时栈顶为“)”,则该运算符进栈(栈中为“-、)”);
取下一个“4”,直接输出(目前输出的是“14”);
取下一个“(”,运算符连续出栈(栈中此时为“-、)”),直到遇见“)”,此时输出“-”(目前输出“14-”,栈为空);
取下一个“*”,既不是“)”,也不是“(”,则转到2.3,进栈(栈为空);
取下一个“3”,直接输出(目前输出“14-3”);
取下一个“+”,此时栈顶为“*”,“+”的优先级比“*”低(2.3.4),则运算符连续出栈(只有一个*出栈,此时栈为空符合2.3.1,继续下一步),“+”进栈;
取下一个“)”,进栈(此时栈中为“)、+”);
取下一个“1”直接输出(目前输出为14-3*1);
取下一个“-”,此时栈顶为“)”,“-”进栈(栈中此时为“-、)、+”);
取下一个“2”,直接输出(目前输出“14-3*12”);
取下一个“(”,运算符连续出栈,直到遇见“)”,此时栈中为“-、)、+”,输出-,且抛弃“)”,此时输出为“14-3*12-”,栈中为“+”;
取下一个“/”,优先级比栈顶“+”高,此运算符进栈;
取下一个“3”,直接输出(此时输出“14-3*12-3”);
取下一个“*”,优先级比栈顶“+”高,此运算符进栈;
取下一个“2”,输出(此时输出“14-3*12-32”);
不在有未处理的运算符,输出栈中剩余元素,结果的“14-3*12-32*/+”;
反转字符串的“+/*23-21*3-41”。
“中序表达式”转换为“前序表达式”、“后序表达式”