Prefix: Similarly, the expression in which the operator appears before the operands is known as prefix expression. For example, +ab, where a and b 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
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).
Related
Contributed by