STACK

栈

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

    public bool IsValid(string s)
    {
        Stack<char> stack = new Stack<char>();

        for(int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            if(c == '(')
                stack.Push(')');
            else if(c == '{')
                stack.Push('}');
            else if(c == '[')
                stack.Push(']');
            else if(stack.Count == 0 || stack.Pop() != c)
                return false;
        }

        return stack.Count == 0;
    }

这个题巧妙的应用了Stack的特性，即后进先出。最初的想法就是发现了左括号，将其压栈，发现又括号的时候，对比此右括号与栈顶的左括号是否匹配，这样会多余一次if判断，因此不如当我们发现了左括号的时候，向堆栈压入对应的右括号，这样当发现有括号的时候，只要与栈顶的内容相同即是匹配的字符串，否则不匹配。

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;
    }