> For the complete documentation index, see [llms.txt](https://stanley7342.gitbook.io/programming/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://stanley7342.gitbook.io/programming/leetcode/20.-valid-parentheses.md).

# 20. Valid Parentheses

## 題目原文

Given a string containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

#### 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
```

## **解題思路**

{% hint style="info" %}

1. 善用[stack](http://www.cplusplus.com/reference/stack/stack/)。
2. 遇到左括弧先push到Stack裡，遇到右括弧再從Stack pop出左括弧。
3. pop出來的左括弧是否對應相對的右括弧。
4. 最後，判斷Stack是否為空。
   {% endhint %}

## 程式解答

```cpp
class Solution 
{
public:
    bool isValid(string s) 
    {
        std::stack<char> p;
        char temp;
        
        if (s.length() % 2 != 0)
            return false;
        
        for (int i = 0; i < s.length(); i++)
        {
            switch (s[i])
            {
                case '(':
                case '[':
                case '{':
                    p.push(s[i]);
                    break;
                case ')':
                    if (!p.size())
                        return false;
                    temp = p.top();
                    p.pop();
                    if (temp != '(')
                        return false;
                    break;
                case ']':
                    if (!p.size())
                        return false;
                    temp = p.top();
                    p.pop();
                    if (temp != '[')
                        return false;
                    break;
                case '}':
                    if (!p.size())
                        return false;
                    temp = p.top();
                    p.pop();
                    if (temp != '{')
                        return false;
                    break;
            }
        }
        if (!p.size())
            return true;
        return false;
    }
};
```