227. Basic Calculator II

Here is the link.

It is easy for me to come out the idea using stack to store operator and operands, and it is always to calculate * and / arithmetic calculations first, and then work on + and - operands.

Here are highlights:

1. Go over the input string once character by character, skip space, push operator into stack, mark * or / operator for immediate processing, parse integer and push into stack as well;
2. In step 1, if number is pushed into stack, and also high operator is found, then pop three times to calculate the result, push back into stack;
3. After iteration of input string, go over the stack, process + or - operator, do calculation;
4. In step 3, I made the mistake on the edge case 1 - 1 + 2, the result should be 2, I calculated 1 - ( 1+ 2) = -2. I did extra checking for operator, if found, then it is popped out, '+' is pushed back in.

public class Solution {
    /// <summary>
        /// Implement the algorithm using data structure - stack 
        /// once *, / sign meet, calculate the value right away; 
        /// once the end of expression, go back to stack and then 
        /// pop one by one to calculate.
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int Calculate(string s)
        {
            if (s == null || s.Length == 0)
                return 0;

            var length = s.Length;
            var stack = new Stack<string>();
            var digits = "0123456789";
            var operators = "+-*/";
            
            // "3+2*2"
            int index = 0;
            var highOperator = false;

            while (index < length)
            {
                var current = s[index];
               
                if (current == ' ')
                {
                    index++;
                    continue; 
                }

                if (operators.IndexOf(current) != -1)
                {
                    stack.Push(current.ToString());
                    index++;

                    if (current == '*' || current == '/')
                    {
                        highOperator = true; 
                    }
                }

                if(digits.IndexOf(current) != -1)
                {
                    int start = index;
                    int end = index;
                    while(index < length && digits.IndexOf(s[index]) != -1)
                    {
                        end = index;
                        index++;                        
                    }

                    var number = s.Substring(start, end - start + 1);

                    stack.Push(number);
                    if (highOperator)
                    {
                        var number2 = Convert.ToInt32(stack.Pop());
                        var operator1 = stack.Pop();
                        var number1 = Convert.ToInt32(stack.Pop());
                        if(operator1[0] == '*')
                        {
                            stack.Push((number1 * number2).ToString());
                        }
                        else 
                        {
                            stack.Push((number1 / number2).ToString());
                        }

                        highOperator = false;
                    }
                }
            }

            while (stack.Count > 0)
            {
                var unknown = stack.Pop();
                var isOperator = unknown.Length == 1 && operators.IndexOf(unknown[0]) != -1;
                if (!isOperator)
                {
                    var number2 = Convert.ToInt32(unknown);

                    if (stack.Count >= 2)
                    {
                        var operator1 = stack.Pop();
                        var number1 = Convert.ToInt32(stack.Pop());

                        //1-1+2
                        if (stack.Count > 0 && stack.Peek().Length == 1 && stack.Peek()[0] == '-')
                        {
                            stack.Pop();
                            stack.Push("+");
                            number1 *= -1; 
                        }

                        if (operator1[0] == '+')
                        {
                            stack.Push((number1 + number2).ToString());
                        }
                        else if (operator1[0] == '-')
                        {
                            stack.Push((number1 - number2).ToString());
                        }
                    }
                    else
                    {
                        return number2;
                    }
                }
            }      

            return 0; 
        }
}