中缀表达式转后缀表达式

1、中缀表达式和后缀表达式

中缀表达式就是我们正常使用的那种，例如：a+b*c

后缀表达式就是abc*+；

为什么要有中缀表达式和后缀表达式呢？

因为中缀表达式便于人们的理解与计算，但是后缀表达式更方便计算机的运算（如二叉树、堆栈的方法计算），因此在读取一个中缀表达式后，将其转化为后缀表达式更有利于计算

2、中缀表达式转后缀表达式

首先假设我们需要转化的中缀表达式为：

a + b * c + ( d * e + f ) * g

其转换成后缀表达式则为 a b c * + d e * f  + g * +

2.1 基于堆栈的方法

转换过程需要用到栈，具体过程如下：

1、从左到右扫描每一个字符,如果遇到操作数，我们就直接将其输出。

2、如果遇到操作符，有如下几种情况

1）如果堆栈是空的，直接将操作符存储到堆栈中 (push)

2）如果该操作符的优先级大于栈顶的操作符，就直接将操作符存储到堆栈中（push）

3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（pop）, 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（push）

• • 优先级  "()" >  "*/"  > "+-"
  • 只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。这一点根据优先级也很好理解，括号的优先级最高

4）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出

3、如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

图解过程如下：

1、从左到右扫描每一个字符,如果遇到操作数，我们就直接将其输出。

2、如果遇到操作符，有如下几种情况

1）如果堆栈是空的，直接将操作符存储到堆栈中 (push)

2）如果该操作符的优先级大于栈顶的操作符，就直接将操作符存储到堆栈中（push）

3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（pop）, 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（push）

遇到『+』号，当前栈中的元素为『*， +』，优先级都不低于当前操作符『+』，故先弹出，『+』再入栈

 遇到『(』号，优先级最高，『(』直接入栈，操作数直接输出

遇到『*』号，优先级高，『(』是栈顶元素，因此直接入栈，操作数直接输出

遇到『+』号，优先级低，『*』是栈顶元素，先出栈，『+』再入栈，操作数直接输出 

 4）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出 

『*』入栈，操作数输出

3、如果我们读到了输入的末尾，则将栈中所有元素依次弹出。 

2.2 括号法

好记又简单，转换过程如下

1、根据运算符的优先级对中缀表达式加括号（有几个运算符就有几对括号）（原本有的括号不用加）

      式子变成：( ( a + ( b * c) ) + ( ( ( d * e ) + f ) * g ) )

2、转换前缀与后缀表达式

　　1）前缀：把运算符号移动到对应的括号前面

      　　则变成：+ ( + ( a * ( b c) ) * ( + ( * ( d e ) f ) g ) )

      　　把括号去掉：+ + a * b c * + * d e f g 即为前缀表达式

      2）后缀：把运算符号移动到对应的括号后面

      　　则变成拉：((a(bc)*)+(((de)*f)+g)*)+

      　　把括号去掉：abc*+de*f+g *+  即为后缀表达式