1106. Parsing A Boolean Expression

Problem : https://leetcode.com/problems/parsing-a-boolean-expression

 

Difficulty : Hard

 

Status : Solved

 

Time : 00:10:56

 

---

 

문제 설명

 

 

불 대수 표현은 true 혹은 fals를 연산하는 표현식이다. 이는 다음과 같은 형태 중 하나로 나타날 수 있다.

 

• 't'는 true로 계산된다.
• 'f'는 false로 계산된다.
• '!(subExpr)'는 내부 표현식 subExpr의 논리적 부정으로 계산된다.
• '&(subExpr1, subExpr2, ... , subExprn)'은 n >=1일때 내부 표현식들 subExpr1, subExpr2, ... subExprn의 논리곱으로 계산된다
• '|(subExpr1, subExpr2, ... , subExprn)'은 n >=1일때  내부 표현식들 subExpr1, subExpr2, ... subExprn의 논리합으로 계산된다.

불 대수 표현을 나타내는 문자열 expression이 주어졌을 때, 그 표현식의 계산값을 구하여라.

주어진 표현식이 유효하며 주어진 규칙들을 따름이 보장된다.

 

---

 

풀이

 

스택 활용 고급편.

연산자들은 '연산자 종류' + '여는 괄호' + '내부 수식들' + '닫는 괄호'를 나타내고, 괄호가 연산 우선순위를 가진다는 점을 눈치챘는가?  그렇다면 가장 내부에 있는 괄호부터 먼저 계산하면 되고, 이는 스택 자료구조로 해결할 수 있다.

수식을 다음과 같이 순회한다고 가정하자.

• 스택에 연산자 혹은 't', 'f'를 저장한다. 연산자가 곧 여는 괄호를 나타낸다고 보아도 좋다(연산자 뒤에는 반드시 여는 괄호가 오므로)
• 닫는 괄호가 등장하면, 연산자가 나올때까지 모든 값을 pop한다.
• 연산자 종류에 따라, pop하여 나온 값들을 계산한다(AND, OR, NOT)
• 계산 결과를 다시 스택에 넣는다.

수식을 모두 순회했을때, 계산식의 유효성이 보장되므로 스택에는 최종 결과물이 남게 된다. 최종 결과물을 bool로 바꾸어 반환하면 된다.

 

풀이 코드

ops = {'!', '&', '|'}

class Solution:
    def notBoolExpr(self, lst) :
        return 't' if lst[0] == 'f' else 'f'
    def andBoolExpr(self, lst) :
        for s in lst :
            if s == 'f' :
                return 'f'
        return 't'

    def orBoolExpr(self, lst) :
        for s in lst :
            if s == 't' :
                return 't'
        return 'f'

    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        for e in expression :
            if e in ops or e == 'f' or e == 't':
                stack.append(e)
            if e == '(' or e == ',':
                continue
            if e == ')' :
                elem = []
                while stack[-1] not in ops :
                    elem.append(stack.pop())
                op = stack.pop()
                if op == '!' :
                    stack.append(self.notBoolExpr(elem))
                elif op == '&' :
                    stack.append(self.andBoolExpr(elem))
                else :
                    stack.append(self.orBoolExpr(elem))
        return stack[0] == 't'