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


相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
175 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
32 1
|
22天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
43 5
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储 分布式计算 Java
存算分离与计算向数据移动:深度解析与Java实现
【11月更文挑战第10天】随着大数据时代的到来,数据量的激增给传统的数据处理架构带来了巨大的挑战。传统的“存算一体”架构,即计算资源与存储资源紧密耦合,在处理海量数据时逐渐显露出其局限性。为了应对这些挑战,存算分离(Disaggregated Storage and Compute Architecture)和计算向数据移动(Compute Moves to Data)两种架构应运而生,成为大数据处理领域的热门技术。
60 2
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
51 4
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
48 0
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
47 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
下一篇
DataWorks