---
description: Stack 就像疊盤子，先進後出
---

# # 20 Valid Parentheses (有圖)

[LeetCode](https://leetcode.com/problems/valid-parentheses/)

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

```
Example 1:

Input: "()"
Output: true
Example 2:

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

/**
 * @param {string} str
 * @return {boolean}
 */
var isValid = function(str) {}
```

### Edge Case

* 中間可能有除了 ( ) { } \[ ] ，其他的符號或字母
* 空值

```
/**
 * Additional examples and edge cases:
 */
console.log( isValid("") ); // true
console.log( isValid("]") ); // false
console.log( isValid("{{[[(())]]}}") ); // true
console.log( isValid("[]{()()[[{}]]}") ); // true
console.log( isValid("a b [d] { (g) (h) i [-[ {;} ]-] }") ); // true
```

### 怎麼解

需要了解 Stack 觀念

* 遇到 { \[ ( 就放到 stack 裡

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LqtRIy64UwWRHZYoDMr%2F-LqtSP36q_9U13ZorIf9%2Fstatck1.jpg?alt=media\&token=8556e898-06c9-42c5-83ce-4009af94f467)

* 遇到 ) ] } 就去抓 stack 看有沒有相對應的 ( \[ {
  * 若沒有就回傳 false
  * 若有就繼續檢查下一個

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LqtRIy64UwWRHZYoDMr%2F-LqtSYa_npzgRdWGg5ID%2Fstack2.jpg?alt=media\&token=aae39b8a-1b22-4cc1-b56c-8dc6e06785ab)

```
function isBalanced(str){
  let current, myStack = [];
  for(let i=0; i<str.length; i++){
    // 把 split 拿掉 string 本身就有 length 的屬性
    current = str[i]
    
    if(current === '{' || current === '[' || current === '('){
      // 直接用 array 原生 push 更簡潔
      myStack.push(current)
    }else if(current === '}'){
      // 就得判斷兩次重覆 所以拿掉剩判斷一次就好
      // pop 回傳移掉那個值, 然後會把 stack 最後面移掉
      return myStack.pop() !== '{';
    }else if(current === ']'){
      return myStack.pop() !== '[';
    }else if(current === ')'){
      return myStack.pop() !== '(';
    }
  }
   return myStack.length === 0;  // [""] true
}
// Runtime faster than 82.86%
```

### 學到什麼

需要對資料結構跟語言本身相當了解才行 (例如，我若不知道 array.pop() 回傳的是被移掉那個值，我可能需要多好幾行程式碼去處理，處裡時同時又讓程式效能更差了 )
