1  import java.util.Stack;
  2  
  3  public class EvaluateExpression {
  4    public static void main(String[] args) {
  5      // Check number of arguments passed
  6      if (args.length != 1) {
  7        System.out.println(
  8          "Usage: java EvaluateExpression \"expression\"");
  9        System.exit(1);
 10      }
 11  
 12      try {
 13        System.out.println(evaluateExpression(args[0]));
 14      }
 15      catch (Exception ex) {
 16        System.out.println("Wrong expression: " + args[0]);
 17      }
 18    }
 19  
 20    /** Evaluate an expression */
 21    public static int evaluateExpression(String expression) {
 22      // Create operandStack to store operands
 23      Stack<Integer> operandStack = new Stack<>();
 24    
 25      // Create operatorStack to store operators
 26      Stack<Character> operatorStack = new Stack<>();
 27    
 28      // Insert blanks around (, ), +, -, /, and *
 29      expression = insertBlanks(expression);
 30  
 31      // Extract operands and operators
 32      String[] tokens = expression.split(" ");
 33  
 34      // Phase 1: Scan tokens
 35      for (String token: tokens) {
 36        if (token.length() == 0) // Blank space
 37          continue; // Back to the while loop to extract the next token
 38        else if (token.charAt(0) == '+' || token.charAt(0) == '-') {
 39          // Process all +, -, *, / in the top of the operator stack 
 40          while (!operatorStack.isEmpty() &&
 41            (operatorStack.peek() == '+' || 
 42             operatorStack.peek() == '-' ||
 43             operatorStack.peek() == '*' ||
 44             operatorStack.peek() == '/')) {
 45            processAnOperator(operandStack, operatorStack);
 46          }
 47  
 48          // Push the + or - operator into the operator stack
 49          operatorStack.push(token.charAt(0));
 50        }
 51        else if (token.charAt(0) == '*' || token.charAt(0) == '/') {
 52          // Process all *, / in the top of the operator stack 
 53          while (!operatorStack.isEmpty() &&
 54            (operatorStack.peek() == '*' ||
 55            operatorStack.peek() == '/')) {
 56            processAnOperator(operandStack, operatorStack);
 57          }
 58  
 59          // Push the * or / operator into the operator stack
 60          operatorStack.push(token.charAt(0));
 61        }
 62        else if (token.trim().charAt(0) == '(') {
 63          operatorStack.push('('); // Push '(' to stack
 64        }
 65        else if (token.trim().charAt(0) == ')') {
 66          // Process all the operators in the stack until seeing '('
 67          while (operatorStack.peek() != '(') {
 68            processAnOperator(operandStack, operatorStack);
 69          }
 70          
 71          operatorStack.pop(); // Pop the '(' symbol from the stack
 72        }
 73        else { // An operand scanned
 74          // Push an operand to the stack
 75          operandStack.push(Integer.valueOf(token));
 76        }
 77      }
 78  
 79      // Phase 2: process all the remaining operators in the stack 
 80      while (!operatorStack.isEmpty()) {
 81        processAnOperator(operandStack, operatorStack);
 82      }
 83  
 84      // Return the result
 85      return operandStack.pop();
 86    }
 87  
 88    /** Process one operator: Take an operator from operatorStack and
 89     *  apply it on the operands in the operandStack */
 90    public static void processAnOperator(
 91        Stack<Integer> operandStack, Stack<Character> operatorStack) {
 92      char op = operatorStack.pop();
 93      int op1 = operandStack.pop();
 94      int op2 = operandStack.pop();
 95      if (op == '+') 
 96        operandStack.push(op2 + op1);
 97      else if (op == '-') 
 98        operandStack.push(op2 - op1);
 99      else if (op == '*') 
100        operandStack.push(op2 * op1);
101      else if (op == '/') 
102        operandStack.push(op2 / op1);
103    }
104    
105    public static String insertBlanks(String s) {
106      String result = "";
107      
108      for (int i = 0; i < s.length(); i++) {
109        if (s.charAt(i) == '(' || s.charAt(i) == ')' || 
110            s.charAt(i) == '+' || s.charAt(i) == '-' ||
111            s.charAt(i) == '*' || s.charAt(i) == '/')
112          result += " " + s.charAt(i) + " ";
113        else
114          result += s.charAt(i);
115      }
116      
117      return result;
118    }
119  }