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.