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。

739. 每日温度

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高，请输入 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。

    public int[] DailyTemperatures(int[] temperatures)
    {
        Stack<int> stack = new Stack<int>();
        int[] ret = new int[temperatures.Length];
        for(int i = 0; i < temperatures.Length; i++)
        {
            while(stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()])
            {
                int index = stack.Pop();
                ret[index] = i - index;
            }
            stack.Push(i);
        }
        return ret;
    }