【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.  

④测试结果:

 

 
  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,如需转载请自行联系原作者


相关文章
|
3天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
77 64
|
12天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
3天前
|
Go
数据结构之 - 深入了解栈数据结构
数据结构之 - 深入了解栈数据结构
13 5
|
12天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
|
12天前
06_用栈来求解汉诺塔问题
06_用栈来求解汉诺塔问题
|
12天前
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
|
12天前
03_如何仅用递归函数和栈操作逆序一个栈
03_如何仅用递归函数和栈操作逆序一个栈
|
1天前
|
算法 Java C语言
【数据结构】后缀(逆波兰)表达式的计算以及中缀转后缀的方法
【数据结构】后缀(逆波兰)表达式的计算以及中缀转后缀的方法
11 0
|
2天前
|
存储 算法 容器
顺序栈的实现
顺序栈的实现
8 0
|
3天前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
6 0