Leetcode Java Parsing A Boolean Expression
업데이트:
문제
코드
class Solution {
public boolean parseBoolExpr(String expression) {
Stack<Character> stack = new Stack<>();
for (char c : expression.toCharArray()) {
if (c == ')') {
Set<Character> seen = new HashSet<>();
while (stack.peek() != '(') {
seen.add(stack.pop());
}
stack.pop();
switch (stack.pop()) {
case '&': stack.push(seen.contains('f') ? 'f' : 't'); break;
case '|': stack.push(seen.contains('t') ? 't' : 'f'); break;
default: stack.push(seen.contains('t') ? 'f' : 't'); break;
}
} else if (c != ',') {
stack.push(c);
}
}
return stack.pop() == 't';
}
}
결과
설명
- 아래의 조건을 만족하는 부울 표현법인 expression이 유효한지를 검증하는 문제이다.
- ‘t’는 true, ‘f’는 false를 의미한다.
- ’!(subExpr)’는 부분 표현법인 subExpr의 논리적 NOT 연산을 의미한다.
- ‘&(subExpr1, subExpr2, …, subExprn)’은 각 부분 표현법인 subExpr1, subExpr2, …, subExprn의 논리적 AND 연산을 의미한다.
-
’ (subExpr1, subExpr2, …, subExprn)’은 각 부분 표현법인 subExpr1, subExpr2, …, subExprn의 논리적 OR 연산을 의미한다.
-
stack은 각 표현식의 값을 순차적으로 넣었다 빼기 위한 변수로, Stack으로 초기화한다.
- expression의 각 문자를 순차적으로 c에 넣어 아래를 수행한다.
- c가 ‘)’ 문자인 경우, 아래를 수행한다.
- seen은 탐색한 문자들을 저장할 변수로, 중복을 제거하기 위해 HashSet으로 초기화하고 stack 내 다음 문자가 ‘(‘ 문자가 아닐 때 까지 seen에 stack의 값을 꺼내 넣어준다.
- stack의 다음 문자인 ‘(‘ 문자를 꺼내 제거해준다.
- stack의 다음 문자가 ‘&’이면 stack에 seen 내 ‘f’ 문자가 존재할 경우 논리적 AND 연산의 결과는 false이므로, ‘f’를 아니면 ‘t’를 넣어준다.
-
stack의 다음 문자가 위의 경우가 아니라 ‘ ‘이면 stack에 seen 내 ‘t’ 문자가 존재할 경우 논리적 OR 연산의 결과는 true이므로, ‘t’를 아니면 ‘f’를 넣어준다. - stack의 다음 문자가 위의 두 경우가 아니라면 stack에 seen 내 ‘t’ 문자가 존재할 경우 반대의 값으로, ‘f’를 아니면 ‘t’를 넣어준다.
- c가 위의 경우가 아니면서 ‘,’ 문자가 아닌 경우, stack에 c를 넣어준다.
- c가 ‘)’ 문자인 경우, 아래를 수행한다.
- stack 내 값을 꺼낸 문자가 ‘t’인지를 검증한 결과를 주어진 문제의 결과로 반환한다.
소스
Sample Code는 여기에서 확인 가능합니다.
댓글남기기