java实现任意四则运算表达式求值算法

本文实例讲述了java实现任意四则运算表达式求值算法。分享给大家供大家参考。具体分析如下：

该程序用于计算任意四则运算表达式。如 4 * ( 10 + 2 ) + 1 的结果应该为 49。
算法说明：

1. 首先定义运算符优先级。我们用一个

Map>

来保存优先级表。这样我们就可以通过下面的方式来计算两个运算符的优先级了：

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栈的栈顶元素即为表达式的值。

算法实现：

public class evaluateexpression {
 // 运算符优先级关系表
 private Map> priorityMap = new HashMap>();
 private linkedStack optStack = new linkedStack();
 // 运算符栈
 private linkedStack numStack = new linkedStack();
 // 操作数栈
 
 public double calcualte(String exp) {
  StringTokenizer st = new StringTokenizer(exp);
  while (st.hasMoreTokens()) {
   String token = st.nextToken();
   process(token);
  }
  return numStack.pop();
 }
 
 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);
 }
   }
  }
 }
 
 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);
  }
 }
 
 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;
 }
 
 private boolean isNumber(char ch) {
  if (ch >= '0' && ch <= '9') {
   return true;
  }
  return false;
 }
 
 public String priority(String op1, String op2) {
  return priorityMap.get(op1).get(op2);
 }
 
 public evaluateexpression() {
  // initialize stack
  optStack.push("#");
  // initialize priority table
  // +
  Map subMap = new HashMap();
  subMap.put("+", ">");
  subMap.put("-", ">");
  subMap.put("*", "<");
  subMap.put("/", "<");
  subMap.put("(", "<");
  subMap.put(")", ">");
  subMap.put("#", ">");
  priorityMap.put("+", subMap);
  // -
  subMap = new HashMap();
  subMap.put("+", ">");
  subMap.put("-", ">");
  subMap.put("*", "<");
  subMap.put("/", "<");
  subMap.put("(", "<");
  subMap.put(")", ">");
  subMap.put("#", ">");
  priorityMap.put("-", subMap);
  // *
  subMap = new HashMap();
  subMap.put("+", ">");
  subMap.put("-", ">");
  subMap.put("*", ">");
  subMap.put("/", ">");
  subMap.put("(", "<");
  subMap.put(")", ">");
  subMap.put("#", ">");
  priorityMap.put("*", subMap);
  // /
  subMap = new HashMap();
  subMap.put("+", ">");
  subMap.put("-", ">");
  subMap.put("*", ">");
  subMap.put("/", ">");
  subMap.put("(", "<");
  subMap.put(")", ">");
  subMap.put("#", ">");
  priorityMap.put("/", subMap);
  // (
  subMap = new HashMap();
  subMap.put("+", "<");
  subMap.put("-", "<");
  subMap.put("*", "<");
  subMap.put("/", "<");
  subMap.put("(", "<");
  subMap.put(")", "=");
  //subMap.put("#", ">");
  priorityMap.put("(", subMap);
  // )
  subMap = new HashMap();
  subMap.put("+", ">");
  subMap.put("-", ">");
  subMap.put("*", ">");
  subMap.put("/", ">");
  //subMap.put("(", "<");
  subMap.put(")", ">");
  subMap.put("#", ">");
  priorityMap.put(")", subMap);
  // #
  subMap = new HashMap();
  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++程序设计有所帮助。