Basic Calculator II

Evaluate + - * / without parentheses in one pass. Remember the operator in front of each number: push for + and -, combine with the stack top at once for * and /.

The idea

Multiplication and division bind tighter than + and -, so do them straight away and leave the additions for the end. A number is complete when you reach the next operator (or the end of the string). Look at the operator that came before it: + pushes the number, - pushes its negative, and * or / pops the top, combines it with the number and pushes the result back. At the end the stack holds only terms to add, so sum it.

Code

public int Calculate(string s) {
    var stack = new Stack<int>();
    int num = 0;
    char op = '+'; // the operator in front of the number being read
    for (int i = 0; i < s.Length; i++) {
        char c = s[i];
        if (char.IsDigit(c)) num = num * 10 + (c - '0');
        if ((!char.IsDigit(c) && c != ' ') || i == s.Length - 1) {
            if (op == '+') stack.Push(num);
            else if (op == '-') stack.Push(-num);
            else if (op == '*') stack.Push(stack.Pop() * num);
            else stack.Push(stack.Pop() / num); // truncates toward zero
            op = c;
            num = 0;
        }
    }
    int sum = 0;
    foreach (int v in stack) sum += v;
    return sum;
}

Tips

• op starts as '+' so the first number is simply pushed.
• Pushing -num turns every subtraction into an addition, which is why a plain sum works at the end.
• C# integer division truncates toward zero, so -14 / 4 is -3, not -4. That matches what the problem asks for.
• Spaces are skipped: they are neither a digit nor an operator, unless one is the very last character.

In the .NET library

c - '0' turns a digit char into its int value, because the digits 0 to 9 have consecutive char codes. Iterating a Stack<int> with foreach visits every item without popping.