---
title: 20.Valid Parentheses
tags: Leetcode,2021
---
# 【LeetCode】 20. Valid Parentheses
## Description
>Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:

>Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

>給一字串只包含 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’ 這些字元，請判斷該字串是否合法。
一個合法字串應該：

>相同類型的左右括號一組 //我不知道怎麼翻譯XD
括號裡面也是正確的括號 //同上
注意，空字串也是合法的字串。

Example:
Example 1:

Input: "()"
Output: true


Example 2:

Input: "()[]{}"
Output: true


Example 3:

Input: "(]"
Output: false


Example 4:

Input: "([)]"
Output: false


Example 5:

Input: "{[]}"
Output: true

## Solution

## Code

public class Solution {
    public bool IsValid(string s) {
          Dictionary<char, char> map = new Dictionary<char, char>()
        {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        
        Stack<char> stack = new Stack<char>();
        for(int i = 0; i < s.Length; i++)
        {
            if (map.ContainsKey(s.ElementAt(i)))
            {
                char top;
                if (stack.Count == 0)
                {
                    top = 'a';
                }
                else
                {
                    top = stack.Pop();
                }
                
                if (top != map[s.ElementAt(i)])
                {
                    return false;
                }
            }
            else
            {
                stack.Push(s.ElementAt(i));
            }
        }
        
        return stack.Count == 0 ? true: false;
    }
}

Stack<char> test = new Stack<char>();
foreach (char i in s.ToCharArray())
{
if (i == '(')
test.Push(')');
else if (i == '[')
test.Push(']');
else if (i == '{')
test.Push('}');
else if (test.Count() == 0 || test.Pop() != i)
return false;
}
return test.Count == 0;