首页 > 代码库 > “中序表达式”转换为“前序表达式”、“后序表达式”

“中序表达式”转换为“前序表达式”、“后序表达式”

 首先看下面所示表格:

 

中序表达式

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”。

“中序表达式”转换为“前序表达式”、“后序表达式”