中綴表達式：a+b*c+(d*e+f)*g

轉換成后綴表達式：abc*+de*f+g*+

轉換步驟：

當讀到一個操作數（如：a）時，立即把它放到輸出中；

當遇到操作符（如：+）時，將其放入棧中；

當遇到右括號時，彈出棧元素直至遇到左括號。將左括號彈出但不輸出；

如果遇到其他操作符[ +, * , ( ?] ，那么彈出棧中的元素直到發現優先級更低的元素為止。有一個例外，除非是處理一個 ) 的時候，否則絕不從棧中移走 ( 。

完整的代碼：

import java.util.Stack;/*** 中綴到后綴的轉換* @author GongQiang**/ public class MiddleToPostExpression {private Stack<Character> stack = new Stack<Character>();/*** @param args** Date :2012-6-26* Author :GongQiang*/public static void main(String[] args) {String middleExp = "a+b*c+(d*e+f)*g";MiddleToPostExpression mtpe = new MiddleToPostExpression();System.out.println( mtpe.transform(middleExp) );}public String transform( String middleExp ){StringBuilder sb = new StringBuilder( middleExp.length() );for( int i=0 ; i<middleExp.length() ; i++ ){char c = middleExp.charAt( i );if( operandChar( c ) ){//空棧-->立即插入if( stack.isEmpty() && !rightBracket(c) ){stack.push( c );}// 操作符級別高 || 棧頂元素是'('else if( getLevel(c) > getLevel( stack.peek() ) || leftBracket( stack.peek() ) ){stack.push( c );}// 當前元素不是')' && 級別比棧頂元素低 && 棧頂元素不是')'else if( !rightBracket(c) && getLevel(c) <= getLevel( stack.peek() ) && !leftBracket( stack.peek() )){while( !stack.isEmpty() && getLevel(c) <= getLevel( stack.peek() ) && !leftBracket( stack.peek() ) ){sb.append( stack.pop() );}stack.push( c );}// 當前元素是')'else if( rightBracket( c ) ){while( !leftBracket( stack.peek() ) ){sb.append( stack.pop() );}stack.pop(); //彈出 '('}}else{sb.append( c );}}//彈出棧中剩下的元素while( !stack.isEmpty() ){sb.append( stack.pop() );}return sb.toString();}/*** 是操作符 ?* @return** Date :2012-6-26* Author :GongQiang*/private boolean operandChar( char c ){char[] operands = { '+', '*', '(', ')' };for( char op : operands ){if( c == op ){return true;}}return false;}private boolean leftBracket( char c ){return c == '(' ? true : false;}private boolean rightBracket( char c ){return c == ')' ? true : false;}private int getLevel( char c ){if( c == '+' ){return 1;}if( c == '*' ){return 2;}if( c == '(' ){return 1024;}// 右括號return -1;} }

總結

以上是生活随笔為你收集整理的中缀到后缀的转换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。