逆波兰表达式算法 java_【算法】表达式求值--逆波兰算法介绍

亦凉 2022-11-03 04:25 199阅读 0赞

packagecom. lulix86 .calc ;importjava. util .ArrayList ;importjava. util .Deque ;importjava. util .HashMap ;importjava. util .Iterator ;importjava. util .LinkedList ;importjava. util .List ;importjava. util .Map ;importjava. util .regex . Matcher;importjava. util .regex . Pattern;public classApp

\{public static voidmain (String \[\] args )

InfixExpression expression= newInfixExpression () ;//(1+8)-(3\*(4-1)) = 0

expression .append ("(") ;

expression .append ("1") ;

expression .append ("+") ;

expression .append ("8") ;

expression .append (")") ;

expression .append ("-") ;

expression .append ("(") ;

expression .append ("3") ;

expression .append ("\*") ;

expression .append ("(") ;

expression .append ("4") ;

expression .append ("-") ;

expression .append ("1") ;

expression .append (")") ;

System . out. println("原始表达式:" +expression );try\{

System . out. println("计算结果是:" +expression. getResultValue () ) ;

\}catch(Exception e)

System . out. println("一定是表达式输入的有问题，请检查后重试") ;

\}/\*\*\* 表达式元素的公父类。表达式元素具体分为：运算符类，操作数类，分界符类。因此这个类有3个子类。 这是一个抽象类。 这个类的作用如下：

\* 1、定义了表达式元素的共同属性：String content，用来存储元素的字符串形式的内容。

\* 2、限定了分界符元素和运算符元素的相关性质：如可取的content值，运算符的优先级等。

\* 2、这个类提供了一些供子类使用的工具函数：isLegalXXXX。

\*@seeExpressionDelimeter

\*@seeExpressionOperator

\*@seeExpressionOperand

\*\*/

abstract classExpressionElement

\{//-----------------------------分界符-----------------------------------//表达式中的分界符：左右圆括号

public static final String LEFT\_PARENTHESES = "(";public static final String RIGHT\_PARENTHESES = ")";protected static booleanisLegalDelimeter (String content)

\{if ( LEFT\_PARENTHESES .equals ( content) ||RIGHT\_PARENTHESES . equals( content ))return true;return false;

\}//-----------------------------运算符-----------------------------------//运算符:这里只用到了常见的这4个运算符

public static final String PLUS = "+";public static final String MINUS = "-";public static final String MULTIPLE = "\*";public static final String DIVIDE = "/";//将运算符 和 他的 优先级 通过 k-v 对存放到 Map中：运算符的优先级分为2个等级，用数字1 和2代表，数值越大，优先级越高

protected static final Map operatorPiority = new HashMap <>();static\{

operatorPiority .put ( PLUS,1) ;

operatorPiority .put ( MINUS,1) ;

operatorPiority .put ( MULTIPLE,2) ;

operatorPiority .put ( DIVIDE,2) ;

\}protected static booleanisLegalOperator (String content)

\{if ( !operatorPiority. containsKey (content ))return false;return true;

\}//-----------------------------操作数-----------------------------------//通过正则表达式校验一个字符串是否是合法的数字 。

protected static booleanisLegalOperand (String content)

Pattern numberPat= Pattern .compile ( "(\\\\+|-)?(\\\\d+\\\\.)?\\\\d+");

Matcher mat=numberPat .matcher ( content) ;if ( !mat. matches ())return false;return true;

\}protected finalString content ;protectedExpressionElement ( String content )

\{this .content =content ;

\}publicString getContent()

\{returncontent ;

@OverridepublicString toString()

\{returncontent . toString() ;

\}/\*\*\* 表达式运算符类。 构造函数私有，不可以自己创建实例，只能用类中预定义的4个静态类对象，分别代表了加减乘除4个运算符。 类对象不可变。

\* 实现了Comparable接口，compareTo方法用来比较2个运算符的优先级。

\*\*/

class ExpressionOperator extends ExpressionElement implements Comparable \{public static final ExpressionOperator OP\_MINUS = newExpressionOperator (ExpressionElement . MINUS) ;public static final ExpressionOperator OP\_PLUS = newExpressionOperator (ExpressionElement . PLUS) ;public static final ExpressionOperator OP\_MULTIPLE = newExpressionOperator (ExpressionElement . MULTIPLE) ;public static final ExpressionOperator OP\_DEVIDE = newExpressionOperator (ExpressionElement . DIVIDE) ;//-----------------------------------------------------

private final int priority ; //运算符的优先级//不可以在类外实例化运算符，不允许创建其它的新的运算符

privateExpressionOperator ( String content )

\{super(content ) ;if ( !isLegalOperator( content ))throw new IllegalArgumentException( "运算符 " + content + " 不是合法的");this .priority =operatorPiority .get ( content) ;

\}public intgetPriority()

\{returnpriority ;

@Overridepublic intcompareTo( ExpressionOperator other )

\{return this . priority -other . priority;

@Overridepublic booleanequals( Object obj )

\{if ( obj == null)return false;if ( obj == this)return true;if ( obj .getClass () != this. getClass ())return false;

ExpressionOperator other=( ExpressionOperator) obj;return this. getContent() . equals( other .getContent ()) ;

\}/\*\*\* 表达式操作数类。

\* 使用double作为数字的存储类型。 不可变类型。 实现了Comparable接口，compareTo方法用来比较2个操作数的大小。

\* 因为操作数是不可枚举的，因此这个类可以创建实例。\*/

class ExpressionOperand extends ExpressionElement implements Comparable \{private final doublevalue ;publicExpressionOperand ( String content )

\{super(content ) ;try\{

value=Double. parseDouble (content ) ;

\}catch(NumberFormatException e)

\{throw new IllegalArgumentException( content + " 不是一个合法的数字");

\}public ExpressionOperand ( doublevalue )

\{super(Double . toString( value ));this .value =value ;

\}public doublegetValue()

\{returnvalue ;

@Overridepublic intcompareTo( ExpressionOperand other )

\{return Double . compare( this.value , other . value) ;

@OverridepublicString toString()

\{return Double . toString( this.value ) ;

\}/\*\*\* 表达式分界符类。 不可变类型。 构造函数私有，不可以自己创建实例，只能用类中预定义的2个静态类对象，分别代表左，右括号。

\*\*/

class ExpressionDelimeter extendsExpressionElement

\{public static final ExpressionDelimeter DM\_LEFT\_PARENTHESES = newExpressionDelimeter (

ExpressionElement . LEFT\_PARENTHESES) ;public static final ExpressionDelimeter DM\_RIGHT\_PARENTHESES = newExpressionDelimeter (

ExpressionElement . RIGHT\_PARENTHESES) ;privateExpressionDelimeter ( String content )

\{super(content ) ;if ( !isLegalDelimeter( content ))throw new IllegalArgumentException( "分界符 " + content + " 不是合法的");

@Overridepublic booleanequals( Object obj )

\{if ( obj == null)return false;if ( obj == this)return true;if ( obj .getClass () != this. getClass ())return false;

ExpressionDelimeter other=( ExpressionDelimeter) obj ;returncontent . equals( other .content ) ;

\}/\*\*\* 表达式类。 你可以把这个类看做是一个存储表达式元素的线性表，因此可以使用appendXXX方法来构造一个表达式。

\* 封装了工具函数 infixToSuffix，用于将中缀表达式转换为后缀表达式。

\* 实现了 Iterable接口，可以迭代ExpressionElement元素对象。\*/

abstract class Expression implements Iterable< ExpressionElement >\{//---------------------------------------------------------------------------//使用ArrayList存储表达式元素

protected final List< ExpressionElement > expression = new ArrayList <>() ;//追加一个表达式元素对象，不可以追加空元素。

public booleanappend( ExpressionElement e )

\{if ( e == null)return false;

expression .add ( e) ;return true;

\}public booleanappend( String content )

\{switch( content )

\{caseExpressionElement . LEFT\_PARENTHESES:

expression .add ( ExpressionDelimeter. DM\_LEFT\_PARENTHESES ) ;break;caseExpressionElement . RIGHT\_PARENTHESES:

expression .add ( ExpressionDelimeter. DM\_RIGHT\_PARENTHESES ) ;break;caseExpressionElement . PLUS:

expression .add ( ExpressionOperator. OP\_PLUS );break;caseExpressionElement . MINUS:

expression .add ( ExpressionOperator. OP\_MINUS );break;caseExpressionElement . MULTIPLE:

expression .add ( ExpressionOperator. OP\_MULTIPLE );break;caseExpressionElement . DIVIDE:

expression .add ( ExpressionOperator. OP\_DEVIDE );break;default:try\{

ExpressionOperand operand= new ExpressionOperand (content ) ; //构造时使用了parseDouble

expression .add ( operand) ;

\}catch(Exception e)

\{return false;

\}return true;

@OverridepublicString toString()

\{boolean firstAdd = true;

StringBuilder sb= newStringBuilder () ;for( ExpressionElement e : expression )

\{if ( !firstAdd)

sb .append (" ") ;

\}else\{

firstAdd= false;

sb .append ( e. toString ());

\}returnsb . toString() ;

@Overridepublic Iterator < ExpressionElement>iterator()

\{returnexpression . iterator() ;

\}public voidclear()

\{this.expression . clear() ;

\}//获取表达式最终的运算的结果

public abstract double getResultValue() throwsException ;

\}class SuffixExpression extendsExpression

\{private doubledoPlus( ExpressionOperand a , ExpressionOperand b )

\{return a . getValue() +b .getValue () ;

\}private doubledoMinus( ExpressionOperand a , ExpressionOperand b )

\{return a . getValue() -b .getValue () ;

\}private doubledoMultiple( ExpressionOperand a , ExpressionOperand b )

\{return a . getValue() \*b .getValue () ;

\}private doubledoDevide( ExpressionOperand a , ExpressionOperand b )

\{return a . getValue() /b .getValue () ;

\}//SuffixExpression 本身已经是一个后缀表达了。getResultValue计算出结果就OK了

@Override

publicdouble getResultValue () throwsException

SimpleStack scalc = new SimpleStack <>() ;for( ExpressionElement e : expression )

\{if ( e instanceofExpressionOperand)

scalc .push (( ExpressionOperand) e) ;

\}else if ( e instanceofExpressionOperator )

ExpressionOperator operator= ( ExpressionOperator) e; //获取这个运算符

ExpressionOperand opf = scalc .pop () ; //弹出二元运算符的第二个操作数

ExpressionOperand ops = scalc .pop () ; //弹出二元运算符的第一个操作数

ExpressionOperand temp = null ; //存储临时运算结果

if ( opf == null || ops == null)throw new Exception( "表达式不合法，不能完成计算") ;if( operator. equals (ExpressionOperator . OP\_PLUS))

temp= newExpressionOperand (doPlus ( ops, opf)) ;

\}else if( operator. equals (ExpressionOperator . OP\_MINUS))

temp= newExpressionOperand (doMinus ( ops, opf)) ;

\}else if( operator. equals (ExpressionOperator . OP\_MULTIPLE))

temp= newExpressionOperand (doMultiple ( ops, opf)) ;

\}else if( operator. equals (ExpressionOperator . OP\_DEVIDE))

temp= newExpressionOperand (doDevide ( ops, opf)) ;

scalc .push ( temp) ;

\}//else if

\}//end foreach

if ( scalc .size () != 1)throw new Exception( "表达式不合法，不能完成计算" ) ; //从 scalc栈中取出最后一个元素就是结果

returnscalc . pop() . getValue() ;

\}class InfixExpression extendsExpression

\{publicSuffixExpression toSuffixExpression()

SuffixExpression suffix= new SuffixExpression () ; //suffix是一个用来存储表达式元素的线性表对象，对应算法中的L

SimpleStack sop = new SimpleStack <>() ; //sop 栈//遍历原始表达式中的每一个元素

for( ExpressionElement e : expression )

\{if ( e instanceof ExpressionOperand) //如果是操作数，则直接追加到后缀表达式suffix中

suffix .append ( e) ;

\}else if ( e instanceof ExpressionDelimeter ) //如果是分界符

\{if ( e. equals (ExpressionDelimeter . DM\_LEFT\_PARENTHESES )) //是 左括号,则直接压栈

sop .push ( e) ;

\}else if ( e. equals (ExpressionDelimeter . DM\_RIGHT\_PARENTHESES )) //是 右括号，则从 sop中弹出与这个括号配对的中间的所有元素，

\{ //并追加到后缀表达式中

while ( ! sop. isEmpty () && !sop. peek (). equals (ExpressionDelimeter . DM\_LEFT\_PARENTHESES ))

suffix .append ( sop. pop ());//将元素出栈，追加到 suffix 表中去

\}if ( !sop. isEmpty ())

sop .pop () ;//将栈顶的( 出栈，丢弃。

\}else if ( e instanceof ExpressionOperator ) //如果是运算符

\{while ( ! sop. isEmpty () && sop . peek() instanceofExpressionOperator&& 0 >=(( ExpressionOperator) e ). compareTo ((ExpressionOperator ) sop . peek()))

suffix .append ( sop. pop ());

sop .push ( e) ;

\}//end of foreach//将 sop栈中剩余的元素全部追加到suffix后

while ( !sop. isEmpty ())

suffix .append ( sop. pop ());

\}returnsuffix ;

@Override

publicdouble getResultValue () throwsException

\{returntoSuffixExpression () .getResultValue () ;

\}/\*\*\*

\* 因为Java集合框架中的Stack类是线程安全的， 但是这里不需要这种特性，为了提高效率，使用双端队列作为内部实现，自己封装成为一个栈数据结构。

\*@seejava.util.Stack