【leetcode】1106. Parsing A Boolean Expression

题目如下:

Return the result of evaluating a given boolean expression, represented as a string.

An expression can either be:

  • "t", evaluating to True;
  • "f", evaluating to False;
  • "!(expr)", evaluating to the logical NOT of the inner expression expr;
  • "&(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressions expr1, expr2, ...;
  • "|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressions expr1, expr2, ...

 

Example 1:

Input: expression = "!(f)"
Output: true

Example 2:

Input: expression = "|(f,t)"
Output: true

Example 3:

Input: expression = "&(t,f)"
Output: false

Example 4:

Input: expression = "|(&(t,f,t),!(t))"
Output: false

 

Constraints:

  • 1 <= expression.length <= 20000
  • expression[i] consists of characters in {'(', ')', '&', '|', '!', 't', 'f', ','}.
  • expression is a valid expression representing a boolean, as given in the description.

解题思路:本题和表达式运算的题目相似。遍历expression并将每一个字符依次入栈,如果遇到')',则找出离栈顶最近的'(',计算出括号之内的表达式的值并将该值入栈,直到expression遍历完成为止。

代码如下:

class Solution(object):
    def parseBoolExpr(self, expression):
        """
        :type expression: str
        :rtype: bool
        """
        stack = []
        expression = expression.replace('t','1')
        expression = expression.replace('f', '0')
        ex = list(expression)
        while len(ex) > 0:
            char = ex.pop(0)
            if char != ')':
                stack.append(char)
                continue
            ts = ''
            while len(stack) > 0:
                item = stack.pop(-1)
                if item == '(':
                    break
                ts += item
            ts_list = ts.split(',')
            and_or = stack.pop(-1)
            if and_or == '!':
                stack.append('1' if ts_list[0] == '0' else '0' )
            elif and_or == '|':
                stack.append('1' if '1' in ts_list else '0')
            else:
                stack.append('0' if '0' in ts_list else '1')
        return stack[0] == '1'

 

上一篇:【Project】基于stm32+mpu6050的体感遥控车


下一篇:1106 Lowest Price in Supply Chain