逆波蘭式的生成算法.doc

逆波蘭式的生成程序（選做）一、實驗目的和要求內(nèi)容：掌握語法分析的基本思想，并用高級語言編寫逆波蘭式的生成程序。 要求：利用逆波蘭式生成算法編寫程序，將從鍵盤中輸入的算術表達式（中綴表達式）轉(zhuǎn)化為逆波蘭式。二、實驗內(nèi)容和原理逆波蘭表達式的生成過程涉及到運算符的優(yōu)先級，下表中列出幾個常用運算符的優(yōu)先關系。常用運算符優(yōu)先關系矩陣右左+-*/()+-*/(逆波蘭表達式生成算法的關鍵在于比較當前運算符與棧頂運算符的優(yōu)先關系，若當前運算符的優(yōu)先關系高于棧頂運算符，則當前運算符進棧，若當前運算符的優(yōu)先級小于棧頂運算符，則棧頂運算符退棧。逆波蘭式生成算法的流程圖 實驗代碼：import java.io.BufferedReader ;import java.io.IOException ;import java.io.InputStreamReader ;public class ReversePolishNotation/*-成員變量的聲明-*/private final char operatorPriorMatrix = , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ; private char infixExpression ; /字符串infix用于表示要處理的中綴表達式private String reversePolishExpression = new String( ) ; /字符串reversePlishExpression用于表示處理結(jié)果逆波蘭式private String analysisStack = new String( ) ; /字符串a(chǎn)nalysisStack用于表示分析棧private int lengthOfInfixExpression = 0 ; /中綴表達式的長度,初始值為0private int count = 0 ; private int matchFlag = 1 ; /用來標識左右括號是否配對正確/*-*/*-成員方法的定義-*/private void init( String str )str = str.trim( ) ;infixExpression = str.toCharArray( ) ;lengthOfInfixExpression = infixExpression.length ;private int operatorJudgement( char currentOperator )int flag = -1 ;switch( currentOperator )case + :flag = 0 ; break ;case - :flag = 1 ; break ;case * :flag = 2 ; break ;case / :flag = 3 ; break ;case ( :flag = 4 ; break ;case ) :flag = 5 ; break ;return flag ; private void convertProcess( String str )init( str ) ;while( true )matchFlag = 0 ;if( count = lengthOfInfixExpression )while( analysisStack.length( ) != 0 )if( analysisStack.charAt( analysisStack.length( ) - 1 ) = ( ) System.out.println( n您輸入的中綴表達式中有無法配對的（括號，請仔細核實! ) ; System.exit( 0 ) ;else reversePolishExpression += analysisStack.charAt( analysisStack.length( ) - 1 ) ;analysisStack = analysisStack.substring( 0 , analysisStack.length( ) -1 ) ;System.out.println( n 逆 波 蘭 式 為： + reversePolishExpression ) ; System.exit( 0 ) ;else if( operatorJudgement( infixExpression count ) = -1 )reversePolishExpression += infixExpression count ;else while( analysisStack.length( ) != 0 )if( operatorPriorMatrixoperatorJudgement(analysisStack.charAt(analysisStack.length()-1 ) )operatorJudgement(infixExpressioncount) = )analysisStack += infixExpression count ; break ;else if( infixExpression count != ) )reversePolishExpression += analysisStack.charAt( analysisStack.length() - 1 ) ;analysisStack = analysisStack.substring( 0 , analysisStack.length( ) -1 ) ;elsewhile( analysisStack.length( ) = 0 | analysisStack.charAt( analysisStack.length() -1 ) != ( )if( analysisStack.length( ) = 0 )System.out.println( n您輸入的中綴表達式中有無法配對的）括號，請仔細核實！ ) ;System.exit( 0 ) ;else reversePolishExpression += analysisStack.charAt( analysisStack.length() - 1 ) ;analysisStack = analysisStack.substring( 0 , analysisStack.length() -1 ) ;if( analysisStack.charAt( analysisStack.length() -1 ) = ( )analysisStack = analysisStack.substring( 0 , analysisStack.length( ) - 1 ) ;matchFlag = 1 ;break ;if( analysisStack.length( ) = 0 )if( infixExpression count != ) )analysisStack += infixExpression count ;else if( matchFlag != 1 )System.out.println( n您輸入的中綴表達式中有無法配對的）括號，請仔細核實！ ) ;System.exit( 0 ) ;count + ; public static void main(String args) throws IOException System.out.print( 請輸入中綴表達式： ) ;BufferedReader