Java实现四则运算表达式求值算法详解
版权申诉
5星 · 超过95%的资源 120 浏览量
更新于2024-09-11
1
收藏 55KB PDF 举报 "本文介绍了如何使用Java实现任意四则运算表达式的求值算法，涉及运算符优先级、辅助栈以及具体的算法流程。通过定义运算符优先级表，利用两个栈（运算符栈和数字栈）来处理表达式，最终计算出正确的结果。"
在Java编程中，解决四则运算表达式求值的问题通常需要使用到栈数据结构和运算符优先级的概念。这个特定的算法设计了一个`priorityMap`来存储运算符的优先级，以便于在处理表达式时比较运算符之间的优先级。例如，乘法和除法的优先级高于加法和减法。`priorityMap`通过`Map<String, Map<String, String>>`来实现，其中键是运算符，值也是一个Map，用于保存每个运算符的相对优先级。
算法的步骤如下：
1. 初始化两个栈：`optStack`用于存放运算符，`numStack`用于存放数字。同时设置一个运算符优先级表`priorityMap`。
2. 逐个扫描输入的四则运算表达式字符串，将每个字符或数字作为token处理。
3. 对于每个token，如果它是数字，直接压入`numStack`；如果是运算符，就从`optStack`顶部取出一个运算符A，比较A与当前token的优先级。
- 如果A的优先级小于token，说明当前运算符优先级更高，将token压入`optStack`。
- 如果A的优先级等于token，这可能表示遇到一对括号，这时需要弹出`optStack`顶部的运算符A。
- 如果A的优先级大于token，说明需要进行一次运算。从`numStack`中弹出两个操作数，再从`optStack`中弹出一个运算符，执行相应的运算，然后将结果压回`numStack`。
4. 当所有token处理完毕，且`optStack`中的运算符只剩下一个起始标记'#'时，`numStack`顶部的元素就是表达式的结果。
在这个实现中，`EvaluateExpression`类还包含了具体的栈操作方法，如压栈、弹栈以及计算操作数的逻辑。由于没有给出完整的代码，具体的`pushOpt`、`popOpt`、`pushNum`、`popNum`和计算操作的实现细节需要根据上下文自行补充。但整体思路是遵循上述的算法流程，确保正确处理括号、运算符优先级以及操作数的计算。
java实现任意四则运算表达式求值算法实现任意四则运算表达式求值算法
本文实例讲述了java实现任意四则运算表达式求值算法。分享给大家供大家参考。具体分析如下：
该程序用于计算任意四则运算表达式。如 4 * ( 10 + 2 ) + 1 的结果应该为 49。
算法说明：
1. 首先定义运算符优先级。我们用一个
Map<String, Map<String, String>>
来保存优先级表。这样我们就可以通过下面的方式来计算两个运算符的优先级了：
/**
* 查表得到op1和op2的优先级
* @param op1 运算符1
* @param op2 运算符2
* @return ">", "<" 或 "="
*/
public String priority(String op1, String op2) {
return priorityMap.get(op1).get(op2);
}
2. 扫描表达式字符串，每次读入一个 token 进行处理。
使用两个辅助栈：optStack用于保存运算符，numStack用于保存操作数. 我们用 ‘#’ 作为表达式的起始和结果标志符。
读入一个token，如果它是数字，则压入numStack栈中；
如果它是运算符，则取出optStack栈的栈顶元素A，将 A 与 token 进行优先级比较。
如果 A < token，则将 token 压入optStack栈。
如果 A = token，则说明 token和A是一对括号，此时将optStack栈的栈顶元素弹出。
如果 A > token，则从numStack中弹出２个操作数，从optStack中弹出1个运算符，并计算结果。
当optStrack栈为空时（即栈顶元素为 ‘#’），numStack栈的栈顶元素即为表达式的值。
算法实现：
/**
* 算术表达式求值。
* 3 + 4 * 12 结果为51
* @author whf
*
*/
public class EvaluateExpression {
// 运算符优先级关系表
private Map<String, Map<String, String>> priorityMap = new HashMap<String, Map<String, String>>();
private LinkedStack<String> optStack = new LinkedStack<String>();
// 运算符栈
private LinkedStack<Double> numStack = new LinkedStack<Double>();
// 操作数栈
/**
* 计算表达式
* @param exp 四则运算表达式, 每个符号必须以空格分隔
* @return
*/
public double calcualte(String exp) {
StringTokenizer st = new StringTokenizer(exp);
while (st.hasMoreTokens()) {
String token = st.nextToken();
process(token);
}
return numStack.pop();
}
/**
* 读入一个符号串。
* 如果是数字，则压入numStack
* 如果是运算符，则将optStack栈顶元素与该运算符进行优先级比较
* 如果栈顶元素优先级低，则将运算符压入optStack栈,如果相同，则弹出左括号，如果高，则取出２个数字，取出一个运算符执行计算，然后将结果压入
numStack栈中
* @param token
下载后可阅读完整内容，剩余3页未读，立即下载
2018-10-07 上传
2010-11-12 上传
点击了解资源详情
2009-10-10 上传
2009-10-27 上传
2021-09-29 上传
2018-10-14 上传
weixin_38638163
- 粉丝: 3
- 资源: 975
我的内容管理
展开
