Re: [閒聊] 每日leetcode
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'
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.188 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729408720.A.14B.html
推
10/20 15:20,
1年前
, 1F
10/20 15:20, 1F
→
10/20 15:22,
1年前
, 2F
10/20 15:22, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1013 之 1554 篇)：