수식 괄호 검사기

문제

사내 계산기 서비스는 사용자가 입력한 수식을 계산하기 전에 괄호부터 검사합니다. 수식에는 변수 이름(영어 소문자), 숫자, 연산자(+, -, *, /)가 섞여 있고, 괄호는 (), [], {} 세 종류를 쓸 수 있습니다.

수식 문자열 expr가 주어질 때, 괄호가 올바르게 사용되었는지 판별하는 solution(expr) 함수를 작성하세요. 올바르면 true, 아니면 false를 반환합니다.

괄호가 올바르다는 것은 다음을 모두 만족한다는 뜻입니다.

1. 열린 괄호는 같은 종류의 닫는 괄호로 닫힌다
2. 나중에 열린 괄호가 먼저 닫힌다 (교차 금지)
3. 닫는 괄호에는 반드시 짝이 되는 열린 괄호가 앞에 있다

괄호가 아닌 문자는 검사에 영향을 주지 않으며, 수식에 괄호가 하나도 없으면 올바른 것으로 봅니다.

예시

제약 조건

• 1 ≤ expr.length ≤ 10,000
• expr는 영어 소문자, 숫자, + - * /, 그리고 ( ) [ ] { } 로만 이루어져 있습니다
• 수식의 계산 가능 여부(연산자 위치 등)는 판단하지 않습니다. 괄호만 검사합니다

시간 복잡도 목표: O(n)