Java implements any four arithmetic expression evaluation algorithm

This article illustrates the Java implementation of any four arithmetic expression evaluation algorithm. Share with you for your reference. Specific analysis is as follows:

This program is used to evaluate any four operational expressions. So 4 times 10 plus 2 plus 1 should be 49.
Algorithm description:

1. First define the operator priority. Let's use a

Map<String, Map<String, String>>

To save the priority table. This allows us to calculate the priority of the two operators in the following way:

public String priority(String op1, String op2) {
 return priorityMap.get(op1).get(op2);
}

2. Scan the expression string and read in one token at a time for processing.

We use two auxiliary stacks: optStack to hold the operator and numStack to hold the operands.

Read in a token and press it into numStack if it is a number.

If it is an operator, take the top element A of the optStack stack and compare A with token in priority.

If A < Token, pushes the token onto the optStack.

If A = token, the token and A are A pair of parentheses, and the top element of the optStack stack pops up.

If A > Token, pops two operands from numStack and one operator from optStack, and evaluates the result.

When the optStrack stack is empty (that is, the top element of the stack is '#'), the top element of the numStack stack is the value of the expression.

Algorithm implementation:

public class EvaluateExpression {
 //Operator priority relation table
 private Map<String, Map<String, String>> priorityMap = new HashMap<String, Map<String, String>>();
 private LinkedStack<String> optStack = new LinkedStack<String>();
 //Operator stack
 private LinkedStack<Double> numStack = new LinkedStack<Double>();
 //The operand stack
 
 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);
   //Skip the decimal point
   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<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);
 }
}

Program test:

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

The result is 49.

Hope that the article described in the C++ programming to help you.