中缀表达式到后缀表达式的转换

中缀到后缀的转换

栈不仅可以用来计算后缀表达式，而且还可以用栈将一个中缀表达式转换为后缀表达式。通过只允许操作+、×、(,),并坚持普通的优先级将问题浓缩成小规模的问题。
当读到一个操作数的时候，立即把它放到输出中。操作数不立即输出，而是放进栈中。当遇到左圆括号时我们也要将其推入栈中。
如果见到一个右括号，那么就将栈元素弹出，将弹出的符号写出直到我们遇到一个相对应的左括号，但这个左括号只被弹出，并不输出。
如果是任何其他的符号( '+' , '*' , '(' , ')' ),那么从栈中弹出栈元素直到发现优先级更低的元素为止。
最后，如果读到输入的末尾，将栈的元素弹出直到该栈变成空栈，将符号写到输出中。
设欲将中缀表达式
		a + b * c + ( d * e + f ) * g
转换为后缀表达式
		a b c * + d e * f + g * +
首先，a被读入，于是它流向输出。然后，‘+’被读入并被放入栈中。接着是b读入并流向输出。这一时刻的状态如下：
	|----|
	|    |         |-----------------|
	|  + |	       | a b             |
	|----|	       |-----------------|
	 Stack		    Output

这时‘*‘号读入。操作符的栈顶元素比’*’的优先级低，故没有输出，‘*'进栈。接着，c被读入并输出。至此，我们有：
	|----|
	|    |
	|  * |		|-----------------|
	|  + |		| a b c           |
	|----|		|-----------------|
	 Stack			Output

后面的符号是一个‘+'号。检查一下栈，需要将’*'从栈弹出并放到输出中；弹出栈中剩下的‘+’号，该运算符不比刚刚遇到的‘+'号优先级低而是有相同的优先级；然后，将刚刚遇到的’+‘号压入栈中。
	|----|
	|    |
	|    |		|-----------------|
	|  + |		| a b c * +       |
	|----|		|-----------------|
	 Stack			Output

下一个被读到的符号是一个‘(',由于有最高的优先级，因此它被放进栈中。然后，d读入并输出。
	|----|
	|    |
	|  ( |		|-----------------|
	|  + |		| a b c * + d     |
	|----|		|-----------------|
	 Stack			Output
	 
继续进行，读到一个’*'。除非正在处理闭括号 ，否则开括号不会从栈中弹出，因此没有输出。下一个字符是‘e',它被读入并输出。
	|----|
	|    |
	|  * |
	|  ( |		|-----------------|
	|  + |		| a b c * + d e   |
	|----|		|-----------------|
	 Stack			Output

再往后读到的符号是’+‘。我们将’*'弹出并输出，然后将‘+’压入栈中。这以后，读到‘f'并输出。
	|----|
	|    |
	|  + |
	|  ( |		|-------------------|
	|  + |		| a b c * + d e * f |
	|----|		|-------------------|
	 Stack			Output
	 
现在，读到一个’)'，因此将栈元素直到’('弹出，将一个‘+’号输出。
	|----|
	|    |		|---------------------|
	|  + |		| a b c * + d e * f + |
	|----|		|---------------------|
	 Stack			 Output
	
下面又读到一个‘*'，该运算符被压入栈中。然后，’g'被读入并输出。
	|----|
	|    |
	|  * |		|-----------------------|
	|  + |		| a b c * + d e * f + g |
	|----|		|-----------------------|
	 Stack			Output
	 
现在输入为空，因此将栈中的符号全部弹出并输出，直到栈变成空栈。
	|----|
	|    |		|---------------------------|
	|    |		| a b c * + d e * f + g * + |
	|----|		|---------------------------|
	 Stack			Output