in DS recategorized by
1,268 views
2 votes
2 votes
in DS recategorized by
by
1.3k views

1 comment

For evaluating prefix expression we need to make a just single scan from right to left once following standard algorithm. So it will take O(n), where n is the number of operators.
0
0

1 Answer

2 votes
2 votes

considering n as length of expression 

now lets evaluates and follow this algo:

begin :

     count=0; one stack/array;

      add to stack if it operator or increment count if operand

      now if count==2 pop top two elements  and top operand and make count=0

      apply operation and push the result into stack and increment count

end:

apply his algo on 

    this prefix: -++xyzl

stack::        -  +  + x   count=1

                 -   +  +  x  y   count=2  and now pop xy and +  add them letrs say m=x+y

                -    +  m  push z        -  +  m  z

               now pop and add them as above y=m+z and put it back on stack

               -  y  l

 and thus complexity is O(n)      

by

1 comment

yes...it should be O(n)...
0
0