STACK

栈

227. 基本计算器II

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7

示例 2:

输入: " 3/2 "
输出: 1

示例 3:

输入: " 3+5 / 2 "
输出: 5

说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

public int Calculate(string s)
{
    if(string.IsNullOrWhiteSpace(s))
        return 0;

    s += "+0";
    Stack<int> nums = new Stack<int>();

    int n = 0;
    char symbol = '+';
    for(int i = 0; i < s.Length; i++)
    {
        char c = s[i];
        if(c == ' ')
            continue;

        if(char.IsDigit(c))
            n = (c - '0') + n * 10;
        else
        {
            if(symbol == '+')
                nums.Push(n);
            else if(symbol == '-')
                nums.Push(-n);
            else if(symbol == '*')
                nums.Push(nums.Pop() * n);
            else if(symbol == '/')
                nums.Push(nums.Pop() / n);
            n = 0;
            symbol = c;
        }
    }

    int res = 0;
    foreach(var num in nums)
        res += num;

    return res;
}

我们从低位到高位遍历字符串，如果是数字，将字符串转成数字，然后当碰到计算符号是+或者-的时候压栈，当遇到*或者/的时候，与栈顶的值计算完再压栈，最后把栈里的数字相加，即得到结果。需要注意的两点，第一，字符串转数字的时候，不要忘了是c - '0'，减去0的ASCII码；第二，符号为-的时候，压栈要压成-n。