FOR FREE MATERIALS

Prefix Evaluation

Back to Programming

Description

Prefix: Similarly, the expression in which the operator appears before the operands is known as prefix expression. For example, +ab, where a and are operands, + is an operator that appears before the operands a and b.

 

Example:

Input:  /+33-+47*+123 (Prefix)

Output:  3

 

Prefix:  /+33-+47*+123 

First reverse the prefix:  321+*74+-33+/

 

Prefix Evaluation:

 

 

Result: 3

Code

TIME COMPLEXITY:

In postfix evaluation, we have to scan n symbols

So, the time complexity of postfix evaluation is O(n)

 

SPACE COMPLEXITY:

We require n stack to evaluate postfix. So, space complexity is O(n)