[알고리즘] Valid Parentheses

포인트

1. 짝을 맞추는 방법 항상 괄호 문제하면 떠올리는 것은 스택을 사용하여 짝을 맞추는 것이다.

 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++

#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> stack;
        for(auto ele : s) {
            if(stack.empty()) stack.push(ele);
            
            if(stack.top()=='['&& ele==']'){
                stack.pop();
                continue;
            }

            if(stack.top()=='('&& ele==')'){
                stack.pop();
                continue;
            }

            if(stack.top()=='{'&& ele=='}'){
                stack.pop();
                continue;
            }


        }
        return stack.empty()==0;
    }
};

python

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if(len(stack)==0):
                stack.append(i)
                continue

            if(stack[-1]=='[' and i==']'):
                stack.pop()
                continue
            if(stack[-1]=='{' and i=='}'):
                stack.pop()
                continue
            if(stack[-1]=='(' and i==')'):
                stack.pop()
                continue

            stack.append(i)
        
        return len(stack)==0

    def isValid(self, s):
        stack = []
        dictionary = {"]":"[", "}":"{", ")":"("}
        for c in s:
            if c in dictionary.values():
                stack.append(c)
            elif c in dictionary.keys():
                if stack == [] or dictionary[c] != stack.pop():
                    return False
            else:
                return False
        return stack == []

뭐 구현의 차이일 수도 있으나 파이썬에서 딕셔너리 자료구조를 사용하여