Movatterモバイル変換


[0]ホーム

URL:


Skip to content
DEV Community
Log in Create account

DEV Community

Ehab Hosam
Ehab Hosam

Posted on

LeetCode in Golang: Parsing A Boolean Expression

This is one of the LeetCode problems I enjoyed solving. I solved it in Golang, and I'm already a Go newbie, who started learning in it since just one week.

LeetCode: Parsing Boolean Expression (Hard)

Image description

Intuition

This problem is another version of implementing a calculator program that takes a string and evaluates it. You have to solve by evaluating the inner parenthesis to the outer ones until you get the final result. These problems are best described by a stack, you're just implementing aCallStack that when opening a new parenthesis, youPush to the stack, and when closing it you justPop from the stack. At the last closing we callEval to get the final result.

We have 3 operations that can be done in ourcalculator, and there are some known facts about them:

  • AND: it's true until you find a false (one false is enough)
  • OR: it's false until you find a true (one true is enough)
  • Not: it's the opposite of the it's argument.

So, we don't need to maintain all the values for each operation to know it's final result. If we're solving anAND, just maintain if you found afalse or not, ifOR, maintain if you found atrue or not, and ifNOT, then it's already gonna be one value that you'll evaluate to it's opposite one.

Approach

We implement a custom struct:CallStack, that has 2 slices, one for the operation and one for the value that we're gonna evaluate.
The call stack has methods:

  • Push: used to push values & operations to the 2 slices we have. Operations push new value to the 2 slices, and values (t orf) just modify the last entered value in the values slice.
  • Pop: remove last value from the 2 slices, evaluate the popped value with the popped operation and use the result to modify thenew last value after popping.
  • Eval: called when it's the last closing parenthesis to evaluate the last remaining value in the values slice with the last remaining operation in the operations slice.

The solution can be more optimized by ending the evaluation of Ands once you find a false, and Ors once you find a true, I'll leave that for you to do if you want :)

Complexity

  • Time complexity:
    O(n)

  • Space complexity:
    O(n)

Code

typeCallStackstruct{operations[]stringvalues[]int}funcNewCallStack()*CallStack{return&CallStack{operations:make([]string,0),values:make([]int,0),}}func(s*CallStack)pushOperation(opstring){s.operations=append(s.operations,op)varnewValintswitchop{caseNot:newVal=0default:newVal=1}s.values=append(s.values,newVal)}func(s*CallStack)pushValue(opstring,charstring){switchop{caseAnd:ifchar=="f"{s.values[len(s.values)-1]=-1}caseOr:ifchar=="t"{s.values[len(s.values)-1]=-1}default:// Notifchar=="t"{s.values[len(s.values)-1]=1}else{s.values[len(s.values)-1]=-1}}}func(s*CallStack)Push(charstring){switchchar{caseNot,And,Or:s.pushOperation(char)default:s.pushValue(s.operations[len(s.operations)-1],char)}}funceval(opstring,valint)bool{switchop{caseAnd:ifval==1{returntrue}else{returnfalse}caseOr:ifval==-1{returntrue}else{returnfalse}default:// Notifval<0{returntrue}else{returnfalse}}}funcaddResult(opstring,valint,resbool)int{switchop{caseAnd:ifres{returnval}else{return-1}caseOr:ifres{return-1}else{returnval}default:// Notifres{return1}else{return-1}}}func(s*CallStack)Pop(){op:=s.operations[len(s.operations)-1]s.operations=s.operations[:len(s.operations)-1]val:=s.values[len(s.values)-1]s.values=s.values[:len(s.values)-1]result:=eval(op,val)currOp:=s.operations[len(s.operations)-1]// current last operationcurrVal:=s.values[len(s.values)-1]// current last values.values[len(s.values)-1]=addResult(currOp,currVal,result)}func(s*CallStack)Eval()bool{// now the length of slices is 1op:=s.operations[0]val:=s.values[0]returneval(op,val)}const(Notstring="!"Andstring="&"Orstring="|")funcparseBoolExpr(expressionstring)bool{stack:=NewCallStack()fori:=0;i<len(expression);i++{char:=string(expression[i])switchchar{case"(",",":// ignore opennings & commascontinuecase")":ifi==len(expression)-1{// it's the last closingreturnstack.Eval()}else{stack.Pop()}default:stack.Push(char)}}returntrue}
Enter fullscreen modeExit fullscreen mode

Top comments(0)

Subscribe
pic
Create template

Templates let you quickly answer FAQs or store snippets for re-use.

Dismiss

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment'spermalink.

For further actions, you may consider blocking this person and/orreporting abuse

A software engineer who's trying to become a better software engineer.
  • Joined

More fromEhab Hosam

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Log in Create account

[8]ページ先頭

©2009-2025 Movatter.jp