逆波兰式的生成算法.doc

逆波兰式的生成程序（选做）一、实验目的和要求内容：掌握语法分析的基本思想，并用高级语言编写逆波兰式的生成程序。 要求：利用逆波兰式生成算法编写程序，将从键盘中输入的算术表达式（中缀表达式）转化为逆波兰式。二、实验内容和原理逆波兰表达式的生成过程涉及到运算符的优先级，下表中列出几个常用运算符的优先关系。常用运算符优先关系矩阵右左+-*/()+-*/(逆波兰表达式生成算法的关键在于比较当前运算符与栈顶运算符的优先关系，若当前运算符的优先关系高于栈顶运算符，则当前运算符进栈，若当前运算符的优先级小于栈顶运算符，则栈顶运算符退栈。逆波兰式生成算法的流程图 实验代码：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用于表示处理结果逆波兰式private String analysisStack = new String( ) ; /字符串analysisStack用于表示分析栈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