Java实现四则运算表达式.docx

Java实现四则运算表达式.docx

《Java实现四则运算表达式.docx》由会员分享，可在线阅读，更多相关《Java实现四则运算表达式.docx（18页珍藏版）》请在冰点文库上搜索。

Java实现四则运算表达式

四则混合运算的算符优先算法Java实现

它们都是对表达式的记法，因此也被称为前缀记法、中缀记法和后缀记法。

它们之间的区别在于运算符相对与操作数的位置不同：

前缀表达式的运算符位于与其相关的操作数之前；中缀和后缀同理。

举例：

（3+4）×5-6就是中缀表达式-×+3456前缀表达式34+5×6-后缀表达式中缀表达式（中缀记法）中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。

中缀表达式是人们常用的算术表示方法。

虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。

对计算机来说，计算前缀或后缀表达式的值非常简单。

前缀表达式（前缀记法、波兰式）

前缀表达式的运算符位于操作数之前。

前缀表达式的计算机求值：

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素op次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

例如前缀表达式“-×+3456”：

（1）从右至左扫描，将6、5、4、3压入堆栈；

（2）遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈；

（3）接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈；

（4）最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

可以看出，用计算机计算前缀表达式的值是很容易的。

将中缀表达式转换为前缀表达式：

遵循以下步骤：

（1）初始化两个栈：

运算符栈S1和储存中间结果的栈S2；

（2）从右至左扫描中缀表达式；

（3）遇到操作数时，将其压入S2；

（4）遇到运算符时，比较其与S1栈顶运算符的优先级：

（4-1）如果S1为空，或栈顶运算符为右括号“）”，则直接将此运算符入栈；

（4-2）否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；

（4-3）否则，将S1栈顶的运算符弹出并压入到S2中，再次转到（4-1）与S1中新的栈顶运算符相比较；

（5）遇到括号时：

（5-1）如果是右括号“）”，则直接压入S1；

（5-2）如果是左括号“（”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；

（6）重复步骤

（2）至（5），直到表达式的最左边；

（7）将S1中剩余的运算符依次弹出并压入S2；

（8）依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

例如，将中缀表达式“1+（（2+3）×4）-5”转换为前缀表达式的过程如下：

扫描到的元素

S2（栈底->栈顶）

S1（栈底->栈顶）

说明

5

5

空

数字，直接入栈

-

5

-

S1为空，运算符直接入栈

）

5

-）

右括号直接入栈

4

54

-）

数字直接入栈

×

54

-）×

S1栈顶是右括号，直接入栈

）

54

-）×）

右括号直接入栈

3

543

-）×）

数字

+

543

-）×）+

S1栈顶是右括号，直接入栈

2

5432

-）×）+

数字

（

5432+

-）×

左括号，弹出运算符直至遇到右括号

（

5432+×

-

同上

+

5432+×

-+

优先级与-相同，入栈

1

5432+×1

-+

数字

到达最左端

5432+×1+-

空

S1中剩余的运算符

因此结果为“-+1×+2345”。

后缀表达式（后缀记法、逆波兰式）

后缀表达式与前缀表达式类似，只是运算符位于操作数之后。

后缀表达式的计算机求值：

与前缀表达式类似，只是顺序是从左至右：

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素op栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

例如后缀表达式“34+5×6-”：

（1）从左至右扫描，将3和4压入堆栈；

（2）遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；

（3）将5入栈；

（4）接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；

（5）将6入栈；

（6）最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

将中缀表达式转换为后缀表达式：

与转换为前缀表达式相似，遵循以下步骤：

（1）初始化两个栈：

运算符栈S1和储存中间结果的栈S2；

（2）从左至右扫描中缀表达式；

（3）遇到操作数时，将其压入S2；

（4）遇到运算符时，比较其与S1栈顶运算符的优先级：

（4-1）如果S1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈；

（4-2）否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；

（4-3）否则，将S1栈顶的运算符弹出并压入到S2中，再次转到（4-1）与S1中新的栈顶运算符相比较；

（5）遇到括号时：

（5-1）如果是左括号“（”，则直接压入S1；

（5-2）如果是右括号“）”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；

（6）重复步骤

（2）至（5），直到表达式的最右边；

（7）将S1中剩余的运算符依次弹出并压入S2；

（8）依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。

例如，将中缀表达式“1+（（2+3）×4）-5”转换为后缀表达式的过程如下：

扫描到的元素

S2（栈底->栈顶）

S1（栈底->栈顶）

说明

1

1

空

数字，直接入栈

+

1

+

S1为空，运算符直接入栈

（

1

+（

左括号，直接入栈

（

1

+（（

同上

2

12

+（（

数字

+

12

+（（+

S1栈顶为左括号，运算符直接入栈

3

123

+（（+

数字

）

123+

+（

右括号，弹出运算符直至遇到左括号

×

123+

+（×

S1栈顶为左括号，运算符直接入栈

4

123+4

+（×

数字

）

123+4×

+

右括号，弹出运算符直至遇到左括号

-

123+4×+

-

-与+优先级相同，因此弹出+，再压入-

5

123+4×+5

-

数字

到达最右端

123+4×+5-

空

S1中剩余的运算符

因此结果为“123+4×+5-”（注意需要逆序输出）。

编写Java程序将一个中缀表达式转换为前缀表达式和后缀表达式，并计算表达式的值。

其中的toPolishNotation（）方法将中缀表达式转换为前缀表达式（波兰式）、toReversePolishNotation（）方法则用于将中缀表达式转换为后缀表达式（逆波兰式）：

注：

下面程序是为了说明上述概念而编写，做了简单的测试

packageqmk.simple_test;

importjava.util.Scanner;

importjava.util.Stack;

/**

*Exampleofconvertinganinfix-expressionto

*PolishNotation（PN）orReversePolishNotation（RPN）.

*Writtenin2011-8-25

*authorQiaoMingkui

*/

publicclassCalculator{

publicstaticfinalStringUSAGE="==usage==\n"

+"inputtheexpressions,andthentheprogram"

+"willcalculatethemandshowtheresult.\n"

+"input'bye'toexit.\n";

/**

*paramargs

*/

publicstaticvoidmain（String[]args）{

System.out.println（USAGE）;

Scannerscanner=newScanner（System.in）;

Stringinput="";

finalStringCLOSE_MARK="bye";

System.out.println（"inputanexpression:

"）;

input=scanner.nextLine（）;

while（input.length（）!

=0

&&!

CLOSE_MARK.equals（（input）））{

System.out.print（"PolishNotation（PN）:

"）;

try{

toPolishNotation（input）;

}catch（NumberFormatExceptione）{

System.out.println（"\ninputerror,notanumber."）;

}catch（IllegalArgumentExceptione）{

System.out.println（"\ninputerror:

"+e.getMessage（））;

}catch（Exceptione）{

System.out.println（"\ninputerror,invalidexpression."）;

}

System.out.print（"ReversePolishNotation（RPN）:

"）;

try{

toReversePolishNotation（input）;

}catch（NumberFormatExceptione）{

System.out.println（"\ninputerror,notanumber."）;

}catch（IllegalArgumentExceptione）{

System.out.println（"\ninputerror:

"+e.getMessage（））;

}catch（Exceptione）{

System.out.println（"\ninputerror,invalidexpression."）;

}

System.out.println（"inputanewexpression:

"）;

input=scanner.nextLine（）;

}

System.out.println（"programexits"）;

}

/**

*parsetheexpression,andcalculateit.

*paraminput

*throwsIllegalArgumentException

*throwsNumberFormatException

*/

privatestaticvoidtoPolishNotation（Stringinput）

throwsIllegalArgumentException,NumberFormatException{

intlen=input.length（）;

charc,tempChar;

Stacks1=newStack（）;

Stacks2=newStack（）;

Stack