[LeetCode] 1106. Parsing A Boolean Expression

https://leetcode.com/problems/parsing-a-boolean-expression/description/?envType=daily-question&envId=2024-10-20

leetcode - Parsing A Boolean Expression

문제 유형: 문자열 처리, 스택, 구현

문제 난이도: Hard

 

문제

A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:

• 't' that evaluates to true.
• 'f' that evaluates to false.
• '!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr.
• '&(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.
• '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.

Given a string expression that represents a boolean expression, return the evaluation of that expression.

It is guaranteed that the given expression is valid and follows the given rules.

 

't'는 true, 'f'는 false, !(subExpr)는 논리 NOT연산, &(...)는 논리 AND연산, |(...)는 논리 OR연산입니다.

불리언 표현식 expression이 주어집니다.

이를 파싱하여 계산한 값을 반환하시오. 유효한 식이 들어오도록 보장되어 있습니다.

 

풀이

Hard로 되어있지만, 사실 그리 하드한 문제는 아니다.

연산자들을 저장할 스택 operators, 피연산자들을 저장할 스택 operands를 저장한다.

표현식을 다음과 같이 순회한다:

  현재 글자가 연산자라면('&, '|', '!'), operators스택에 넣는다.

  현재 글자가 여는 괄호인 '('라면, operands스택에 넣는다. 연산의 적용범위를 알기위해 넣어줘야 한다.

  현재 글자가 't'또는 'f'라면, operands스택에 넣는다.

  현재 글자가 ')'라면, 연산을 할 차례이다.

    !이라면, operands스택의 톱에서 문자를 하나 빼서 반전시킨다.

    &이라면, operands스택의 톱에서 문자를 하나 뺀거로 시작해서 스택의 톱이 '('가 나오기 직전까지 AND연산을 누적한다.

    |이라면, operands스택의 톱에서 문자를 하나 뺀거로 시작해서 스택의 톱이 '('가 나오기 직전까지 OR연산을 누적한다.

    각 연산이 종료되고, '('를 없애기위해 스택의 톱을 한번 pop하고, 논리연산된 값을 push한다.

 

표현식을 한 번 탐색하고 나면, 스택의 톱에는 최종결과가 남아있다. 이게 't'이면 true를, 아니면, 'false'를 반환하면 된다.

 

코드

C++

class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> operators;
        stack<char> operands;

        for(const char &ch : expression) {
            if(ch == '&' || ch == '|' || ch == '!') {
                operators.push(ch);
            } else if(ch == '(') {
                operands.push(ch);
            } else if(ch == 't' || ch == 'f') {
                operands.push(ch);
            } else if(ch == ')') {
                char op = operators.top();
                operators.pop();
                char res = operands.top();
                operands.pop();
                
                switch (op) {
                    case '!': {
                        res = res == 't'? 'f' : 't';
                        break;
                    }
                    case '&' : {
                        while(operands.top() != '(') {
                            res = res == 't' && operands.top() == 't'? 't':'f';
                            operands.pop();
                        }
                        break;
                    }
                    case '|': {
                        while(operands.top() != '(') {
                            res = res == 't' || operands.top() == 't'? 't':'f';
                            operands.pop();
                        }
                        break;
                    }
                }
                operands.pop();
                operands.push(res);
            }
        }

        return operands.top() == 't';
    }
};