Problem:

Implement a basic calculator to evaluate a simple expression string.

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

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7" 3/2 " = 1" 3+5 / 2 " = 5

 

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

 

Analysis:

Unlike the Calculator 1, this quesion is acutally much easier!!! You should do through a very tricky method.To understand this problem, we should firstly understand the puzzle around this problem.for equation like "22 - 31 * 52 + 22"when we reach 31, we do not know whether to use it with 22, thus "22 - 31" or keep it for late usage.In this situation, we apparenlty should not use it with 22 as "22 - 31", but use it with 52 as "31 * 52".But we really could not know such information, until we reach "*" and get "52". Can we delay such calculation?Yes!!!!Why not decide the usage of 31 until we reach "+" after 52, when we have already know "*" and "52". We can do it!!!!Suppose when reach a sign character "+ - * /", we have already know the number and the sign right before the number. (sign) num---------------------------------------------------------------------------------------------------------if (sign == '+')    stack.push(num);if (sign == '-')    stack.push(-1 * num);if (sign == '*')    stack.push(stack.pop() * num);if (sign == '/')    stack.push(stack.pop() / num);iff the sign is '*' or '/', we combine the preivous two numbers together. " (-31) * 52" as single number. (Just like we do the calculation manually. Right!!!)----------------------------------------------------------------------------------------------------------Sklls:1. how to get the num?char c = s.charAt(i);if (Character.isDigit(c))     num = num*10 + (c - '0');Note: Character.isDigit(c) is very elegant!2. how to tackle the last num?if (i == s.length() - 1) {...}3. how to get the number before the current num.stack.pop()

Solution:

public class Solution {    public int calculate(String s) {        if (s == null || s.length() == 0)            return 0;        Stack
     
       stack = new Stack
      
        ();        int num = 0;        char sign = '+';        for (int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            if (Character.isDigit(c))                 num = num*10 + (c - '0');            if ((c != ' ' && !Character.isDigit(c)) || i == s.length() - 1) {                if (sign == '+')                    stack.push(num);                if (sign == '-')                    stack.push(-1 * num);                if (sign == '*')                    stack.push(stack.pop() * num);                if (sign == '/')                    stack.push(stack.pop() / num);                sign = c;                num = 0;            }        }        int ret = 0;        for (int i : stack) {            ret += i;        }        return ret;    }}