本文实例讲述了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 */ private void process(String token) { while (false == "#".equals(optStack.getTop()) || false == token.equals("#")) { // token is numeric if (true == isNumber(token)) { numStack.push(Double.parseDouble(token)); break; // token is operator } else { String priority = priority(optStack.getTop(), token); if ("<".equals(priority)) { optStack.push(token); break; } else if ("=".equals(priority)) { optStack.pop(); break; } else { double res = calculate(optStack.pop(), numStack.pop(), numStack.pop()); numStack.push(res); } } } } /** * 执行四则运算 * @param opt * @param n1 * @param n2 * @return */ private double calculate(String opt, double n1, double n2) { if ("+".equals(opt)) { return n2 + n1; } else if ("-".equals(opt)) { return n2 - n1; } else if ("*".equals(opt)) { return n2 * n1; } else if ("/".equals(opt)) { return n2 / n1; } else { throw new RuntimeException("unsupported operator:" + opt); } } /** * 检查一个String是否为数字 * @param token * @return */ private boolean isNumber(String token) { int LEN = token.length(); for (int ix = 0 ; ix < LEN ; ++ix) { char ch = token.charAt(ix); // 跳过小数点 if (ch == '.') { continue; } if (false == isNumber(ch)) { return false; } } return true; } /** * 检查一个字符是否为数字 * @param ch * @return */ private boolean isNumber(char ch) { if (ch >= '0' && ch <= '9') { return true; } return false; } /** * 查表得到op1和op2的优先级 * @param op1 运算符1 * @param op2 运算符2 * @return ">", "<" 或 "=" */ public String priority(String op1, String op2) { return priorityMap.get(op1).get(op2); } /** * 构造方法，初始化优先级表 */ public EvaluateExpression() { // initialize stack optStack.push("#"); // initialize priority table // + Map<String, String> subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("+", subMap); // - subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("-", subMap); // * subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("*", subMap); // / subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("/", subMap); // ( subMap = new HashMap<String, String>(); subMap.put("+", "<"); subMap.put("-", "<"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", "="); //subMap.put("#", ">"); priorityMap.put("(", subMap); // ) subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); //subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put(")", subMap); // # subMap = new HashMap<String, String>(); subMap.put("+", "<"); subMap.put("-", "<"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); //subMap.put(")", ">"); subMap.put("#", "="); priorityMap.put("#", subMap); } }

程序测试：

String exp = "4 * ( 10 + 2 ) + 1 #"; EvaluateExpression ee = new EvaluateExpression(); out.println(ee.calcualte(exp));

运行结果为 49。

希望本文所述对大家的C++程序设计有所帮助。