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.

Dark Mode

1,268 views

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)