[例子和习题出自数据结构(严蔚敏版), 本人使用Java进行实现. 转载请注明作者和出处, 如有谬误, 欢迎在评论中指正. ]
对整数表达式求值. 表达式中可能包含+-*/四则运算, 以及括号, 比如:4 + 2 * 3 - 10 / 5, (1+2) * (4 + 5) - (9 / 7)等.
思路: 将括号之间的内容当做子表达式求值, 得出子表达式的结果后就可以去掉括号了.
使用optr栈存储运算符, opnd栈存储操作数. 解析表达式, 如果得到操作数就存入opnd栈中, 如果得到运算符, 就根据所得的运算符和optr栈顶运算符的优先级比较结果, 进行相应的操作.
1. 定义优先级和优先级表
- /**
- * 运算符优先权
- */
- public enum Precede {
- /**
- * 优先权高
- */
- LARGER,
- /**
- * 优先权低
- */
- LESS;
- /**
- * 优先级表
- * + - * /
- * + > > < <
- * - > > < <
- * * > > > >
- * / > > > >
- */
- private static Precede[][] precedes = new Precede[4][4];
- static {
- // 根据优先级表初始化precedes数组
- for (int i = 0; i < precedes.length; i++) {
- for (int j = 0; j < precedes[i].length; j++) {
- if ((i == 0 || i == 1) && j > 1) {
- precedes[i][j] = LESS;
- } else {
- precedes[i][j] = LARGER;
- }
- }
- }
- }
- /**
- * 判断2个运算符的优先级
- */
- public static Precede judgePrecede(char operand1, char operand2) {
- int left = getIndex(operand1);
- int right = getIndex(operand2);
- return precedes[left][right];
- }
- /**
- * 获取运算符对应的数组索引
- */
- private static int getIndex(char operand) {
- switch (operand) {
- case '+':
- return 0;
- case '-':
- return 1;
- case '*':
- return 2;
- case '/':
- return 3;
- default:
- throw new IllegalArgumentException();
- }
- }
- }
2. 表达式求值
- /**
- * 整数表达式运算
- */
- public class EvaluateExpression {
- /**
- * 表达式
- */
- private String expression;
- /**
- * 最初的表达式
- */
- private String initExpression;
- /**
- * 运算符栈
- */
- private MyStack<Character> optr = new MyArrayStack<Character>();
- /**
- * 操作数栈
- */
- private MyStack<Integer> opnd = new MyArrayStack<Integer>();
- /**
- * 表明下一个是否应该是数字
- */
- private boolean numberNext;
- public EvaluateExpression(String expression) {
- this.expression = expression;
- this.initExpression = expression;
- numberNext = true;
- }
- /**
- * 求值
- */
- public Integer evaluate() {
- delBlank();
- handleParentheses();
- while (true) {
- if ("".equals(expression)) {
- break;
- }
- if (expression.matches("^-?\\d+.*$") && numberNext) {
- opnd.push(getInteger());
- continue;
- } else {
- Character operand = expression.charAt(0);
- numberNext = true;
- expression = expression.substring(1);
- Character pop;
if(optr.isEmpty()){
pop=null;
}else{
pop = optr.pop();
} - if (pop == null) {
- optr.push(operand);
- continue;
- } else {
- Precede precede = Precede.judgePrecede(pop, operand);
- switch (precede) {
- // 优先级高时运算前2个操作数
- case LARGER: {
- optr.push(operand);
- Integer next = opnd.pop();
- Integer last = opnd.pop();
- evaluateNow(last, pop, next);
- break;
- }
- // 优先级低时运算前一个操作数和后一个操作数
- case LESS: {
- optr.push(pop);
- Integer last = opnd.pop();
- Integer next = getInteger();
- evaluateNow(last, operand, next);
- break;
- }
- }
- }
- }
- }
- // 运算结果
- Integer result = null;
- if (optr.length() == 0 && opnd.length() == 1) {
- result = opnd.pop();
- } else if (optr.length() == 1 && opnd.length() == 2) {
- Integer next = opnd.pop();
- Integer last = opnd.pop();
- evaluateNow(last, optr.pop(), next);
- result = opnd.pop();
- } else {
- throw new RuntimeException();
- }
- return result;
- }
- /**
- * 进行实际的运算,并将结果入栈
- */
- private void evaluateNow(Integer last, Character operand, Integer next) {
- switch (operand) {
- case '+':
- opnd.push(last + next);
- break;
- case '-':
- opnd.push(last - next);
- break;
- case '*':
- opnd.push(last * next);
- break;
- case '/':
- opnd.push(last / next);
- break;
- }
- }
- /**
- * 获得表达式开头部分的整数
- */
- private Integer getInteger() {
- StringBuilder sb = new StringBuilder();
- int count = 0; // 整数位
- boolean lessZero = false; // 是否是负数
- if (expression.startsWith("-")) {
- sb.append("-");
- count++;
- lessZero = true;
- }
- int i = (lessZero ? 1 : 0);
- for (; i < expression.length(); i++) {
- char c = expression.charAt(i);
- if (c >= '0' && c <= '9') {
- sb.append(c);
- count++;
- } else {
- break;
- }
- }
- expression = expression.substring(count);
- numberNext = false;
- return Integer.valueOf(sb.toString());
- }
- /**
- * 处理括号. 将括号内的字符串作为子表达式计算.
- */
- private void handleParentheses() {
- while (expression.contains("(")) {
- // 左括号的索引
- int left = 0;
- // 右括号的索引
- int right = 0;
- // 左括号的数量
- int count = 0;
- // 求出左括号索引
- left = expression.indexOf('(');
- // 求出对应的右括号索引
- for (int i = left; i < expression.length(); i++) {
- char c = expression.charAt(i);
- if (c == ')') {
- count--;
- // count为0时才是对应的右括号
- if (count == 0) {
- right = i;
- break;
- }
- } else if (c == '(') {
- count++;
- } else {
- continue;
- }
- }
- // 左右括号之间是一个子表达式, 计算子表达式的值,并根据结果构造出新的表达式
- EvaluateExpression evaluateExpression = new EvaluateExpression(expression.substring(left + 1, right));
- expression = expression.substring(0, left) + evaluateExpression.evaluate()
- + expression.substring(right + 1);
- }
- }
- /**
- * 删除表达式中的空白字符
- */
- private void delBlank() {
- expression = expression.replaceAll("\\s", "");
- }
- @Override
- public String toString() {
- return initExpression;
- }
- }
3. 进行测试
- @Test
- public void testEvaluate() {
- EvaluateExpression expression = new EvaluateExpression("1 + 2 ");
- System.out.println(expression + " = " + expression.evaluate());
- expression = new EvaluateExpression("4 + 2 * 3 - 10 / 5");
- System.out.println(expression + " = " + expression.evaluate());
- expression = new EvaluateExpression("(1+2) * (4 + 5) - (9 / 7)");
- System.out.println(expression + " = " + expression.evaluate());
- expression = new EvaluateExpression("(1 + (3 * (4 - 9)))");
- System.out.println(expression + " = " + expression.evaluate());
- expression = new EvaluateExpression("(1 + (3 * (4 - 9))) + (3 * (2 + 3))");
- System.out.println(expression + " = " + expression.evaluate());
- }
测试的结果为:
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
可见结果是正确的.
相关推荐
6. **Java实现** 在Java中,我们可以使用`Scanner`类读取输入表达式,`Stack<Double>`存储数字,`Stack<Character>`存储操作符。用循环遍历输入,根据字符类型执行相应的操作。 7. **C++实现** 在C++中,可以使用...
这些文章可能详细介绍了不同方法,包括自定义解析器或者使用第三方库来实现表达式求值。 "java字符串转换成算术表达式(用jep) - 刘亚飞 - ITeye技术网站.htm" 提到了"jep",这是一个开源的Java库,全称为Java ...
Java中缀表达式求值 ...* Java实现中缀表达式求值的步骤。 * `CalculateExpression` 类的实现细节。 Java中缀表达式求值是计算机科学中一个重要的概念,掌握该概念对于开发高效的计算程序非常重要。
总结来说,Java实现表达式求值涉及到字符串处理、数据结构(栈)、抽象语法树的构建、运算符优先级的处理以及设计模式的应用。这个过程不仅可以帮助理解编程语言的核心概念,也锻炼了解决复杂问题的能力。
调用该类的静态方法CalString(String s),参数为要求值的表达式,CalString(String s)将返回计算结果,或者是出错信息。 设计思路:见代码的注释文档 反馈:本程序对以上支持的内容经过大量测试,所谓“只有...
java模拟栈实现表达式求值代码.zip可以完全实现多种功能的计算,采用了算符优先关系计算表达式的值。 注意:表达式的形式为 #表达式# 的形式,两个#号只表示表达式的开始和结束,真正的表达式在中间部分。。。。
在Java编程语言中,表达式求值是一项基本且重要的任务,尤其在动态计算、脚本解析或编译器实现等领域。"Java表达式求值2.0"可能是指一个优化过的版本,用于更高效地处理Java中的数学或逻辑表达式。这个版本可能是...
后缀表达式求值:使用Java语言实现后缀表达式的求值算法; 后缀表达式求值:使用Java语言实现后缀表达式的求值算法; 后缀表达式求值:使用Java语言实现后缀表达式的求值算法; 后缀表达式求值:使用Java语言实现...
实现一个算术表达式求值器可以让我们掌握到字符串处理、数据结构(如栈)以及算法设计等多个方面的知识,这些都是Java程序员日常工作中不可或缺的技能。通过这个项目,你不仅能学会如何处理动态的算术表达式,还能...
- **C++/Java**:可以使用递归函数或者栈来实现表达式求值,例如使用`std::stack`或自定义堆栈类。 - **Python**:Python的`eval()`函数可以直接执行字符串表达式,但可能存在安全风险。自定义求值函数更安全,...
调用该类的静态方法CalString(String s),参数为要求值的表达式,CalString(String s)将返回计算结果,或者是出错信息。 设计思路:见代码的注释文档 反馈:本程序对以上支持的内容经过大量测试,所谓“只有...
在本话题中,我们将深入探讨如何使用数据结构,特别是栈,来实现算术表达式的求值。这个主题对于理解程序设计方法学至关重要,特别是在《程序设计方法学》(第2版)中,作者胡正国可能有专门的章节或习题讨论此技术...
### 基于栈实现算术表达式求值的原理与算法 在计算机科学领域,栈是一种非常重要的数据结构,其遵循先进后出(LIFO)原则,即最后进入的数据最先被处理。栈广泛应用于多种场景,其中之一就是利用栈来求解算术表达式...
综上所述,这个压缩包文件提供了一个用Java实现的后缀表达式求值工具,包含了处理单个和批量表达式的功能,并使用了Scanner和PrintWriter进行输入输出交互。对于理解和实现表达式求值算法,以及熟悉Java I/O操作,这...
7. **代码实现**:使用某种编程语言(如C++、Python、Java等)实现表达式求值算法。代码应该清晰、可读性强,遵循良好的编程规范,以便于他人理解和维护。 8. **测试与调试**:为了确保算法的正确性,需要设计各种...
在本场景中,我们关注的是基于栈的数据结构来实现表达式求值,这是许多编译器和解释器设计的基础部分。下面将详细讨论表达式求值的原理、栈的使用以及具体实现步骤。 首先,表达式求值可以分为前缀表达式、中缀...
**Java实现** 在Java中,可以创建一个Calculator类来完成这个任务。Calculator类可以包含一个Stack类,用于存储运算符和操作数。解析表达式时,可以使用Scanner类读取输入的中缀表达式,然后调用相应的转换和计算...
在实际编程实现中,可以使用各种编程语言(如C++、Java、Python等)来编写表达式求值器,关键在于理解和正确实现上述算法。同时,为了处理浮点数和错误检查,可能还需要额外的逻辑。这个过程不仅锻炼了对数据结构和...
在本话题中,我们将深入探讨堆栈在表达式求值中的应用,以及如何利用堆栈实现一个简单的表达式求值器。 表达式求值是计算机科学中的一个重要概念,尤其是在编译原理和解释器设计中。它涉及将数学或逻辑表达式转换为...
这里我们将深入探讨如何运用堆栈数据结构来实现表达式求值,特别是针对单字符的计算、括号匹配以及处理运算符的优先级。 首先,我们要理解堆栈的基本操作。堆栈是一种“后进先出”(LIFO)的数据结构,它的主要操作...