`

java实现表达式求值

阅读更多

[例子和习题出自数据结构(严蔚敏版), 本人使用Java进行实现.  转载请注明作者和出处,  如有谬误, 欢迎在评论中指正. ]

对整数表达式求值. 表达式中可能包含+-*/四则运算, 以及括号, 比如:4 + 2 * 3 - 10 / 5, (1+2) * (4 + 5) - (9 / 7)等.

思路: 将括号之间的内容当做子表达式求值, 得出子表达式的结果后就可以去掉括号了.

使用optr栈存储运算符, opnd栈存储操作数. 解析表达式, 如果得到操作数就存入opnd栈中, 如果得到运算符, 就根据所得的运算符和optr栈顶运算符的优先级比较结果, 进行相应的操作.

 

1. 定义优先级和优先级表

Java代码   收藏代码
  1. /** 
  2.  * 运算符优先权 
  3.  */  
  4. public enum Precede {  
  5.     /** 
  6.      * 优先权高 
  7.      */  
  8.     LARGER,  
  9.     /** 
  10.      * 优先权低 
  11.      */  
  12.     LESS;  
  13.   
  14.     /** 
  15.      * 优先级表 
  16.      *      +   -   *   / 
  17.      *  +   >    >    <    < 
  18.      *  -   >    >    <    < 
  19.      *  *   >    >    >    > 
  20.      *  /   >    >    >    > 
  21.      */  
  22.     private static Precede[][] precedes = new Precede[4][4];  
  23.   
  24.     static {  
  25.         // 根据优先级表初始化precedes数组  
  26.         for (int i = 0; i < precedes.length; i++) {  
  27.             for (int j = 0; j < precedes[i].length; j++) {  
  28.                 if ((i == 0 || i == 1) && j > 1) {  
  29.                     precedes[i][j] = LESS;  
  30.                 } else {  
  31.                     precedes[i][j] = LARGER;  
  32.                 }  
  33.             }  
  34.         }  
  35.     }  
  36.   
  37.     /** 
  38.      * 判断2个运算符的优先级 
  39.      */  
  40.     public static Precede judgePrecede(char operand1, char operand2) {  
  41.         int left = getIndex(operand1);  
  42.         int right = getIndex(operand2);  
  43.         return precedes[left][right];  
  44.     }  
  45.   
  46.     /** 
  47.      * 获取运算符对应的数组索引 
  48.      */  
  49.     private static int getIndex(char operand) {  
  50.         switch (operand) {  
  51.         case '+':  
  52.             return 0;  
  53.         case '-':  
  54.             return 1;  
  55.         case '*':  
  56.             return 2;  
  57.         case '/':  
  58.             return 3;  
  59.         default:  
  60.             throw new IllegalArgumentException();  
  61.         }  
  62.     }  
  63. }  

 

2. 表达式求值

Java代码   收藏代码
  1. /** 
  2.  * 整数表达式运算 
  3.  */  
  4. public class EvaluateExpression {  
  5.     /** 
  6.      * 表达式 
  7.      */  
  8.     private String expression;  
  9.     /** 
  10.      * 最初的表达式 
  11.      */  
  12.     private String initExpression;  
  13.     /** 
  14.      * 运算符栈 
  15.      */  
  16.     private MyStack<Character> optr = new MyArrayStack<Character>();  
  17.     /** 
  18.      * 操作数栈 
  19.      */  
  20.     private MyStack<Integer> opnd = new MyArrayStack<Integer>();  
  21.     /** 
  22.      * 表明下一个是否应该是数字  
  23.      */  
  24.     private boolean numberNext;  
  25.   
  26.     public EvaluateExpression(String expression) {  
  27.         this.expression = expression;  
  28.         this.initExpression = expression;  
  29.         numberNext = true;  
  30.     }  
  31.   
  32.     /** 
  33.      * 求值 
  34.      */  
  35.     public Integer evaluate() {  
  36.         delBlank();  
  37.         handleParentheses();  
  38.   
  39.         while (true) {  
  40.             if ("".equals(expression)) {  
  41.                 break;  
  42.             }  
  43.               
  44.             if (expression.matches("^-?\\d+.*$") && numberNext) {  
  45.                 opnd.push(getInteger());  
  46.                 continue;  
  47.             } else {  
  48.                 Character operand = expression.charAt(0);  
  49.                 numberNext = true;  
  50.                 expression = expression.substring(1);  
  51.                 Character pop;
                     if(optr.isEmpty()){
                      pop=null;
                     }else{
                      pop = optr.pop();
                     }
  52.   
  53.                 if (pop == null) {  
  54.                     optr.push(operand);  
  55.                     continue;  
  56.                 } else {  
  57.                     Precede precede = Precede.judgePrecede(pop, operand);  
  58.                     switch (precede) {  
  59.                     // 优先级高时运算前2个操作数  
  60.                     case LARGER: {  
  61.                         optr.push(operand);  
  62.                         Integer next = opnd.pop();  
  63.                         Integer last = opnd.pop();  
  64.                         evaluateNow(last, pop, next);  
  65.                         break;  
  66.                     }  
  67.                     // 优先级低时运算前一个操作数和后一个操作数  
  68.                     case LESS: {  
  69.                         optr.push(pop);  
  70.                         Integer last = opnd.pop();  
  71.                         Integer next = getInteger();  
  72.                         evaluateNow(last, operand, next);  
  73.                         break;  
  74.                     }  
  75.                     }  
  76.                 }  
  77.             }  
  78.         }  
  79.   
  80.         // 运算结果  
  81.         Integer result = null;  
  82.         if (optr.length() == 0 && opnd.length() == 1) {  
  83.             result = opnd.pop();  
  84.         } else if (optr.length() == 1 && opnd.length() == 2) {  
  85.             Integer next = opnd.pop();  
  86.             Integer last = opnd.pop();  
  87.             evaluateNow(last, optr.pop(), next);  
  88.             result = opnd.pop();  
  89.         } else {  
  90.             throw new RuntimeException();  
  91.         }  
  92.         return result;  
  93.     }  
  94.   
  95.     /** 
  96.      * 进行实际的运算,并将结果入栈 
  97.      */  
  98.     private void evaluateNow(Integer last, Character operand, Integer next) {  
  99.         switch (operand) {  
  100.         case '+':  
  101.             opnd.push(last + next);  
  102.             break;  
  103.         case '-':  
  104.             opnd.push(last - next);  
  105.             break;  
  106.         case '*':  
  107.             opnd.push(last * next);  
  108.             break;  
  109.         case '/':  
  110.             opnd.push(last / next);  
  111.             break;  
  112.         }  
  113.     }  
  114.   
  115.     /** 
  116.      * 获得表达式开头部分的整数 
  117.      */  
  118.     private Integer getInteger() {  
  119.         StringBuilder sb = new StringBuilder();  
  120.         int count = 0// 整数位  
  121.         boolean lessZero = false// 是否是负数  
  122.           
  123.         if (expression.startsWith("-")) {  
  124.             sb.append("-");  
  125.             count++;  
  126.             lessZero = true;  
  127.         }  
  128.           
  129.         int i = (lessZero ? 1 : 0);  
  130.         for (; i < expression.length(); i++) {  
  131.             char c = expression.charAt(i);  
  132.             if (c >= '0' && c <= '9') {  
  133.                 sb.append(c);  
  134.                 count++;  
  135.             } else {  
  136.                 break;  
  137.             }  
  138.         }  
  139.         expression = expression.substring(count);  
  140.         numberNext = false;  
  141.         return Integer.valueOf(sb.toString());  
  142.     }  
  143.   
  144.     /** 
  145.      * 处理括号. 将括号内的字符串作为子表达式计算. 
  146.      */  
  147.     private void handleParentheses() {  
  148.         while (expression.contains("(")) {  
  149.             // 左括号的索引  
  150.             int left = 0;  
  151.             // 右括号的索引  
  152.             int right = 0;  
  153.             // 左括号的数量  
  154.             int count = 0;  
  155.   
  156.             // 求出左括号索引  
  157.             left = expression.indexOf('(');  
  158.   
  159.             // 求出对应的右括号索引  
  160.             for (int i = left; i < expression.length(); i++) {  
  161.                 char c = expression.charAt(i);  
  162.                 if (c == ')') {  
  163.                     count--;  
  164.                     // count为0时才是对应的右括号  
  165.                     if (count == 0) {  
  166.                         right = i;  
  167.                         break;  
  168.                     }  
  169.                 } else if (c == '(') {  
  170.                     count++;  
  171.                 } else {  
  172.                     continue;  
  173.                 }  
  174.             }  
  175.             // 左右括号之间是一个子表达式, 计算子表达式的值,并根据结果构造出新的表达式  
  176.             EvaluateExpression evaluateExpression = new EvaluateExpression(expression.substring(left + 1, right));  
  177.             expression = expression.substring(0, left) + evaluateExpression.evaluate()  
  178.                     + expression.substring(right + 1);  
  179.         }  
  180.     }  
  181.   
  182.     /** 
  183.      * 删除表达式中的空白字符 
  184.      */  
  185.     private void delBlank() {  
  186.         expression = expression.replaceAll("\\s""");  
  187.     }  
  188.       
  189.     @Override  
  190.     public String toString() {  
  191.         return initExpression;  
  192.     }  
  193. }  

 

3. 进行测试

 

Java代码   收藏代码
  1. @Test  
  2. public void testEvaluate() {  
  3.     EvaluateExpression expression = new EvaluateExpression("1 + 2 ");  
  4.     System.out.println(expression + " = " + expression.evaluate());  
  5.       
  6.     expression = new EvaluateExpression("4 + 2 * 3 - 10 / 5");  
  7.     System.out.println(expression + " = " + expression.evaluate());  
  8.       
  9.     expression = new EvaluateExpression("(1+2) * (4 + 5) - (9 / 7)");  
  10.     System.out.println(expression + " = " + expression.evaluate());  
  11.       
  12.     expression = new EvaluateExpression("(1 + (3 * (4 - 9)))");  
  13.     System.out.println(expression + " = " + expression.evaluate());  
  14.       
  15.     expression = new EvaluateExpression("(1 + (3 * (4 - 9))) + (3 * (2 + 3))");  
  16.     System.out.println(expression + " = " + expression.evaluate());  
  17. }  

测试的结果为:

1 + 2  = 3

4 + 2 * 3 - 10 / 5 = 8

(1+2) * (4 + 5) - (9 / 7) = 26

(1 + (3 * (4 - 9))) = -14

(1 + (3 * (4 - 9))) + (3 * (2 + 3)) = 1

 

可见结果是正确的.

分享到:
评论

相关推荐

    java c++表达式求值(带括号和小数点)

    6. **Java实现** 在Java中,我们可以使用`Scanner`类读取输入表达式,`Stack&lt;Double&gt;`存储数字,`Stack&lt;Character&gt;`存储操作符。用循环遍历输入,根据字符类型执行相应的操作。 7. **C++实现** 在C++中,可以使用...

    java算术表达式求值

    这些文章可能详细介绍了不同方法,包括自定义解析器或者使用第三方库来实现表达式求值。 "java字符串转换成算术表达式(用jep) - 刘亚飞 - ITeye技术网站.htm" 提到了"jep",这是一个开源的Java库,全称为Java ...

    Java中缀表达式求值

    Java中缀表达式求值 ...* Java实现中缀表达式求值的步骤。 * `CalculateExpression` 类的实现细节。 Java中缀表达式求值是计算机科学中一个重要的概念,掌握该概念对于开发高效的计算程序非常重要。

    表达式求值计算(java实现)

    总结来说,Java实现表达式求值涉及到字符串处理、数据结构(栈)、抽象语法树的构建、运算符优先级的处理以及设计模式的应用。这个过程不仅可以帮助理解编程语言的核心概念,也锻炼了解决复杂问题的能力。

    表达式求值 Java实现(改)

    调用该类的静态方法CalString(String s),参数为要求值的表达式,CalString(String s)将返回计算结果,或者是出错信息。 设计思路:见代码的注释文档 反馈:本程序对以上支持的内容经过大量测试,所谓“只有...

    java模拟栈实现表达式求值代码.zip

    java模拟栈实现表达式求值代码.zip可以完全实现多种功能的计算,采用了算符优先关系计算表达式的值。 注意:表达式的形式为 #表达式# 的形式,两个#号只表示表达式的开始和结束,真正的表达式在中间部分。。。。

    Java表达式求值2.0

    在Java编程语言中,表达式求值是一项基本且重要的任务,尤其在动态计算、脚本解析或编译器实现等领域。"Java表达式求值2.0"可能是指一个优化过的版本,用于更高效地处理Java中的数学或逻辑表达式。这个版本可能是...

    使用Java语言实现后缀表达式的求值算法

    后缀表达式求值:使用Java语言实现后缀表达式的求值算法; 后缀表达式求值:使用Java语言实现后缀表达式的求值算法; 后缀表达式求值:使用Java语言实现后缀表达式的求值算法; 后缀表达式求值:使用Java语言实现...

    java 算术表达式求值器

    实现一个算术表达式求值器可以让我们掌握到字符串处理、数据结构(如栈)以及算法设计等多个方面的知识,这些都是Java程序员日常工作中不可或缺的技能。通过这个项目,你不仅能学会如何处理动态的算术表达式,还能...

    表达式求值 算法 代码 报告 流程图

    - **C++/Java**:可以使用递归函数或者栈来实现表达式求值,例如使用`std::stack`或自定义堆栈类。 - **Python**:Python的`eval()`函数可以直接执行字符串表达式,但可能存在安全风险。自定义求值函数更安全,...

    表达式求值 Java实现

    调用该类的静态方法CalString(String s),参数为要求值的表达式,CalString(String s)将返回计算结果,或者是出错信息。 设计思路:见代码的注释文档 反馈:本程序对以上支持的内容经过大量测试,所谓“只有...

    表达式求值

    在本话题中,我们将深入探讨如何使用数据结构,特别是栈,来实现算术表达式的求值。这个主题对于理解程序设计方法学至关重要,特别是在《程序设计方法学》(第2版)中,作者胡正国可能有专门的章节或习题讨论此技术...

    掌握基于栈实现算术表达式求值的原理和算法

    ### 基于栈实现算术表达式求值的原理与算法 在计算机科学领域,栈是一种非常重要的数据结构,其遵循先进后出(LIFO)原则,即最后进入的数据最先被处理。栈广泛应用于多种场景,其中之一就是利用栈来求解算术表达式...

    后缀表达式求值包及其使用

    综上所述,这个压缩包文件提供了一个用Java实现的后缀表达式求值工具,包含了处理单个和批量表达式的功能,并使用了Scanner和PrintWriter进行输入输出交互。对于理解和实现表达式求值算法,以及熟悉Java I/O操作,这...

    含变量的表达式求值问题.rar

    7. **代码实现**:使用某种编程语言(如C++、Python、Java等)实现表达式求值算法。代码应该清晰、可读性强,遵循良好的编程规范,以便于他人理解和维护。 8. **测试与调试**:为了确保算法的正确性,需要设计各种...

    表达式求值_表达式求值栈_wrotey1q_栈表达式求值_

    在本场景中,我们关注的是基于栈的数据结构来实现表达式求值,这是许多编译器和解释器设计的基础部分。下面将详细讨论表达式求值的原理、栈的使用以及具体实现步骤。 首先,表达式求值可以分为前缀表达式、中缀...

    JAVA数据结构复杂表达式求值

    **Java实现** 在Java中,可以创建一个Calculator类来完成这个任务。Calculator类可以包含一个Stack类,用于存储运算符和操作数。解析表达式时,可以使用Scanner类读取输入的中缀表达式,然后调用相应的转换和计算...

    表达式求值,加减乘除混合运算

    在实际编程实现中,可以使用各种编程语言(如C++、Java、Python等)来编写表达式求值器,关键在于理解和正确实现上述算法。同时,为了处理浮点数和错误检查,可能还需要额外的逻辑。这个过程不仅锻炼了对数据结构和...

    数据结构表达式求值

    在本话题中,我们将深入探讨堆栈在表达式求值中的应用,以及如何利用堆栈实现一个简单的表达式求值器。 表达式求值是计算机科学中的一个重要概念,尤其是在编译原理和解释器设计中。它涉及将数学或逻辑表达式转换为...

    运用堆栈实现表达式求值

    这里我们将深入探讨如何运用堆栈数据结构来实现表达式求值,特别是针对单字符的计算、括号匹配以及处理运算符的优先级。 首先,我们要理解堆栈的基本操作。堆栈是一种“后进先出”(LIFO)的数据结构,它的主要操作...

Global site tag (gtag.js) - Google Analytics