【Java数据结构的实现】之系列三栈的实现(使用栈计算后缀表达式)

【Java数据结构的实现】之系列三栈的实现(使用栈计算后缀表达式)

上讲介绍了栈的介绍，最后并给出了栈的抽象数据类型

1.1本章学习目标

• 中、后缀表达式简介
• 后缀表达式的实现

本文介绍了栈的实例--使用栈计算后缀表达式：

1.2 中、后缀表达式简介

①中缀表达式：

       通常，算术表达式写作中缀表达式，，什么是中缀表达式呢？中缀表达式就是：操作符位于操作数之间。

如下形式：

<操作数><操作符><操作数>

例如表达式：1+2*3，计算时，我们根据表达式的优先规则来计算。其结果是7而不是9.

那什么是后缀表达式呢？

②后缀表达式：

后缀表达式就是：操作符位于两个操作数之后，后缀表达式的形式如下：

<操作数><操作数><操作符>

如下所示：

1. 1 2 - 等价于1-2  
2.  

③使用后缀表达式的优点：

      后缀表达式比中缀表达式更容易计算，因为它不用考虑优先规则和括弧，表达式中的操作数和操作符的顺序就足以完成计算。

因此程序设计语言编辑器和运行时环境在其内部中往往使用后缀表达式。

④后缀表达式的计算规则：

        后缀表达式的计算过程可以概括如下：

从左到右扫描整个表达式，把每个操作符应用到其之前两个相邻的操作数，并计算该结果，剩下的表达式以此类推。

1+2*3

可以转换成后缀表达式如下：

1 2 3 * +

计算过程如下：

1 2*3 + --> 1 6 + -->7

更复杂的后缀表达式，亦是如此规则。由此可以发现，栈是用于计算后缀表达式的理想数据结构。

1.3 后缀表达式的实现

①程序设计的思路：

1. /**  
2.      * 从左到右扫描表达式，以此标识出每个符号（操作数或操作符）。如果是操作数，  
3.      * 则把它压入栈中。如果是操作符，则从栈中弹出两个元素，  
4.      * 并把该操作符应用在这两个元素只上，然后把操作结果压入栈中。  
5.      * 当到达表达式的末尾时，栈中所神域的元素就是该表达式的计算结果。  
6.      * @param expr 后缀表达式  
7.      * @return int 后缀表达式的值  
8.      * */ 

程序运行时，会提示用户反复输入操作数和操作符，中间已空格隔开。

②程序关键部位均有详细的注释！

1. import java.util.Stack;  
2.  
3. /**  
4.  * 计算后缀表达式，假定操作数都是常量  
5.  * */ 
6. public class PostfixEvaluator {  
7.     /**+号标识*/ 
8.     private final char ADD = '+';  
9.     /**-号标识*/ 
10.     private final char SUBTRACT = '-';  
11.     /***号标识*/ 
12.     private final char MULTIPLY = '*';  
13.     /**除号标识*/ 
14.     private final char DIVIDE = '/';  
15.     /**栈*/ 
16.     private Stack<Integer> stack;  
17.     /**创建一个新栈*/ 
18.     public PostfixEvaluator(){  
19.         stack = new Stack<Integer>();  
20.     }  
21.     /**  
22.      * 从左到右扫描表达式，以此标识出每个符号（操作数或操作符）。如果是操作数，  
23.      * 则把它压入栈中。如果是操作符，则从栈中弹出两个元素，  
24.      * 并把该操作符应用在这两个元素只上，然后把操作结果压入栈中。  
25.      * 当到达表达式的末尾时，栈中所神域的元素就是该表达式的计算结果。  
26.      * @param expr 后缀表达式  
27.      * @return int 后缀表达式的值  
28.      * */ 
29.  
30.     public int evaluate(String expr){  
31.         int op1,op2,result=0;  
32.         String token;  
33.         //将字符串分解,\s 匹配任何空白字符，包括空格、制表符、换页符等。   
34.         String[] tokenizer = expr.split("\\s");  
35.         for (int x = 0; x < tokenizer.length; x++){  
36.             System.out.print(tokenizer[x]+" ");//输出  
37.             token = tokenizer[x];  
38.             if(isOperator(token)){//判断是操作符，则出栈两个操作数  
39.                 op2 = (stack.pop()).intValue();  
40.                 op1 = (stack.pop()).intValue();  
41.                 result = evalSingleOp (token.charAt(0),op1,op2);//计算结果  
42.                 stack.push(new Integer(result));//把计算结果压入栈中  
43.             }else {  
44.                 stack.push(new Integer(Integer.parseInt(token)));//压入操作数  
45.             }  
46.         }  
47.         return result;  
48.     }  
49.     /**  
50.      * 计算  
51.      * @param1 op1 第一个操作数  
52.      * @prama2 op2第二个操作数  
53.      * @return 计算的结果  
54.      *   
55.      * */ 
56.     private int evalSingleOp(char operation, int op1, int op2) {  
57.         int result = 0;  
58.         switch(operation)  
59.         {  
60.             case ADD:  
61.                 result = op1+op2;  
62.                 break;  
63.             case SUBTRACT:  
64.                 result = op1-op2;  
65.                 break;  
66.             case MULTIPLY:  
67.                 result = op1*op2;  
68.                 break;  
69.             case DIVIDE:  
70.                 result = op1/op2;  
71.                 break;  
72.         }  
73.         return result;  
74.     }  
75.     /**  
76.      * 判断是否为操作符  
77.      * @param token  
78.      * @return boolean   
79.      * */ 
80.     private boolean isOperator(String token) {  
81.            
82.         return (token.equals("+")||token.equals("-")||  
83.                token.equals("*")||token.equals("/"));  
84.     }  
85. }  

③ 测试方法：

1. import java.util.Scanner;  
2.  
3. /**  
4.  *   
5.  * 计算后缀表达式  
6.  * */ 
7. public class Postfix {  
8.  
9.     /**  
10.      * @param args  
11.      */ 
12.     public static void main(String[] args) {  
13.         String expression,again;  
14.         int result;  
15.         try {  
16.             Scanner in = new Scanner(System.in);  
17.             do {  
18.                 PostfixEvaluator evaluator = new PostfixEvaluator();  
19.                 System.out.println("请输入一个后缀表达式");  
20.                 expression = in.nextLine();  
21.                 result = evaluator.evaluate(expression);//  
22.                 System.out.println();  
23.                 System.out.println("计算结果为："+result);  
24.                 System.out.println("计算另外一个表达式【Y/N】?：");  
25.                 again = in.nextLine();  
26.                 if(again.equalsIgnoreCase("n")){  
27.                     System.out.println("计算退出！");  
28.                 }  
29.                 System.out.println();  
30.             }while (again.equalsIgnoreCase("y"));  
31.         }catch(Exception e) {  
32.             e.printStackTrace();  
33.             System.out.println("输入异常，请正确输入后缀表达式，并以空格区分");  
34.         }  
35.  
36.     }  
37.       
38.  
39. } 

④测试结果：

1. /**  
2.  * 请输入一个后缀表达式  
3. 3 4 * 2 5 + - 4 * 2 /  
4. 3 4 * 2 5 + - 4 * 2 /   
5. 计算结果为：10  
6. 计算另外一个表达式【Y/N】?：  
7.  *   
8.  * */ 

 本文转自 w156445045 51CTO博客，原文链接：http://blog.51cto.com/enetq/713534，如需转载请自行联系原作者