逆波蘭式的生成算法.doc

逆波蘭式的生成程序（選做）一、實(shí)驗(yàn)?zāi)康暮鸵髢?nèi)容：掌握語(yǔ)法分析的基本思想，并用高級(jí)語(yǔ)言編寫(xiě)逆波蘭式的生成程序。 要求：利用逆波蘭式生成算法編寫(xiě)程序，將從鍵盤(pán)中輸入的算術(shù)表達(dá)式（中綴表達(dá)式）轉(zhuǎn)化為逆波蘭式。二、實(shí)驗(yàn)內(nèi)容和原理逆波蘭表達(dá)式的生成過(guò)程涉及到運(yùn)算符的優(yōu)先級(jí)，下表中列出幾個(gè)常用運(yùn)算符的優(yōu)先關(guān)系。常用運(yùn)算符優(yōu)先關(guān)系矩陣右左+-*/()+-*/(逆波蘭表達(dá)式生成算法的關(guān)鍵在于比較當(dāng)前運(yùn)算符與棧頂運(yùn)算符的優(yōu)先關(guān)系，若當(dāng)前運(yùn)算符的優(yōu)先關(guān)系高于棧頂運(yùn)算符，則當(dāng)前運(yùn)算符進(jìn)棧，若當(dāng)前運(yùn)算符的優(yōu)先級(jí)小于棧頂運(yùn)算符，則棧頂運(yùn)算符退棧。逆波蘭式生成算法的流程圖 實(shí)驗(yàn)代碼：import java.io.BufferedReader ;import java.io.IOException ;import java.io.InputStreamReader ;public class ReversePolishNotation/*-成員變量的聲明-*/private final char operatorPriorMatrix = , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ; private char infixExpression ; /字符串infix用于表示要處理的中綴表達(dá)式private String reversePolishExpression = new String( ) ; /字符串reversePlishExpression用于表示處理結(jié)果逆波蘭式private String analysisStack = new String( ) ; /字符串a(chǎn)nalysisStack用于表示分析棧private int lengthOfInfixExpression = 0 ; /中綴表達(dá)式的長(zhǎng)度,初始值為0private int count = 0 ; private int matchFlag = 1 ; /用來(lái)標(biāo)識(shí)左右括號(hào)是否配對(duì)正確/*-*/*-成員方法的定義-*/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您輸入的中綴表達(dá)式中有無(wú)法配對(duì)的（括號(hào)，請(qǐng)仔細(xì)核實(shí)! ) ; 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您輸入的中綴表達(dá)式中有無(wú)法配對(duì)的）括號(hào)，請(qǐng)仔細(xì)核實(shí)！ ) ;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您輸入的中綴表達(dá)式中有無(wú)法配對(duì)的）括號(hào)，請(qǐng)仔細(xì)核實(shí)！ ) ;System.exit( 0 ) ;count + ; public static void main(String args) throws IOException System.out.print( 請(qǐng)輸入中綴表達(dá)式： ) ;BufferedReader