772. Basic Calculator

772. Basic Calculator III

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Note: Do not use the eval built-in library function.

https://leetcode.com/problems/basic-calculator/description/
https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/
https://www.geeksforgeeks.org/stack-set-4-evaluation-postfix-expression/

Idea:

1. convert infix notation to postfix notation

Maintain a ArrayList and Stack. ArrayList store the tokens of the posfix. Stack store the operator.

If the char is digit, scan to the last continuous digit, convert it to number and add it to ArrayList.

If the char is (, push it into stack.

If the char is ), keep popping the stack into the arrayList until it reaches )(don't forget to pop the ) from the stack) 

If the char is operator

   if its precedence is smaller than (equal )the stack peek precedence, keep popping the elements from stack into the arrayList util its precedence is larger than the stack peek.

   when this char precedence is larger than the stack peek precedence, push this char into the stack

2. Evaluate the postfix notation.

// convert infix notation to reverse polish notation: Shunting-yard algorithm

 //because the number may be more than 1 digit, so use arraylist.
 public List<String> infix2PostfixList(String infix) {
  ArrayList<String> res = new ArrayList<String>();
  Stack<Character> s = new Stack<Character>();
  int n = infix.length();
  for(int i = 0; i < n; i++) {
   char c = infix.charAt(i);
   if(Character.isDigit(c)) {
    int num = 0;
    while(Character.isDigit(c) && i < n) {
     num = num * 10 + (c - '0');
     i++;
     c = infix.charAt(i);
    }
    res.add(Integer.toString(num));
   }else if(c == '(') {
    s.push(c);
   }else if(c == ')') {
    while(!s.isEmpty()&&s.peek()!='(') {
     res.add(String.valueOf(c));
    }
    s.pop();
   }else{
    while(!s.isEmpty()&&this.priority(s.peek()) >= this.priority(c)) {
     res.add(String.valueOf(c));
    }
    s.push(c);
   }
  }
  
  while(!s.isEmpty()) {
   res.add(String.valueOf(s.pop()));
  }
  return res;
 }
 
 public int priority(char c) {
  if(c == '+' || c == '-') {
   return 1;
  }else if(c == '*' || c == '/') {
   return 2;
  }
  return 0;
 }

        //evaluation postfix notation

 public static final HashSet<String> operators = new HashSet<String>(Arrays.asList("*","/","-","+"));
 public int evaluationPostfix(List<String> postfix) {
  Stack<Integer> stack = new Stack<Integer>();
  for(String token : postfix) {
   if(operators.contains(token)) {
    int op1 = stack.pop();
    int op2 = stack.pop();
    stack.push(eval(op1,op2,token));
   }else {
    stack.push(Integer.parseInt(token));
   }
  }
  return stack.pop();
 }
 
 private int eval(int op1, int op2, String operator) {
  switch(operator) {
  case "*":
   return op1 * op2;
  case "/":
   return op1 / op2;
  case "+":
   return op1 + op2;
  default:
   return op1 - op2;
  }
 }