1106. Parsing A Boolean Expression
給一串布林表示式的字串expression
包含'('、')'、','、't'、'f'、'|'、'&'、'!'
請回傳最終的結果
思路:
建立兩個stack
stack_op放運算子 : | 、 ! 、 &
stack_val放'f'、't'、'('
當遇到')'時就去stack_op裡面pop出運算子
接著從stack_val裡面一直pop出來計算直到遇到'('
最後把計算出來的結果push進stack_val
就這樣一直遍歷完expression
stack_val[0]就會是答案
golang code :
func parseBoolExpr(expression string) bool {
stack_op := []byte{}
stack_val := []byte{}
n, i := len(expression), 0
for i < n {
if expression[i] == '|' || expression[i] == '!' || expression[i] == '&' {
stack_op = append(stack_op, expression[i])
} else if expression[i] == '(' || expression[i] == 'f' || expression[i] == '
t' {
stack_val = append(stack_val, expression[i])
} else if expression[i] == ')' {
val := 0
if stack_val[len(stack_val)-1] == 't' {
val = 1
}
stack_val = stack_val[:len(stack_val)-1]
op := stack_op[len(stack_op)-1]
stack_op = stack_op[:len(stack_op)-1]
switch op {
case '|':
for stack_val[len(stack_val)-1] != '(' {
if stack_val[len(stack_val)-1] == 'f' {
val |= 0
} else {
val |= 1
}
stack_val = stack_val[:len(stack_val)-1]
}
case '&':
for stack_val[len(stack_val)-1] != '(' {
if stack_val[len(stack_val)-1] == 'f' {
val &= 0
} else {
val &= 1
}
stack_val = stack_val[:len(stack_val)-1]
}
case '!':
val ^= 1
}
stack_val = stack_val[:len(stack_val)-1]
if val == 1 {
stack_val = append(stack_val, 't')
} else {
stack_val = append(stack_val, 'f')
}
}
i++
}
return stack_val[0] == 't'
}