Prefix notation is a notation in which operators are written before their operands. For example, the expressions given are in prefix notation / * A + B C D.
Point to consider
- Permitted operands: A,B,C,D means any real number is permitted.
- Permitted operators: +,-, *, /, ^(exponentiation)
- Blanks are permitted in the expression
- Parenthesis are permitted
Prefix and Postfix expressions can be evaluated faster in comparison to an infix expression because we don’t need to process any brackets or follow operator precedence rule. In postfix and prefix expressions which ever operator comes before will be evaluated first, irrespective of its priority. Also, there are no brackets in these expressions. As long as we can guarantee that a valid prefix or postfix expression is used, it can be evaluated with correctness.
Algorithm to evaluate prefix expression
Step 1: Start Evaluating expression from right to left or reverse the expression
Step 2: If a character is an operand push it to Stack
Step 3: If the character is an operator
pop two elements from the Stack.
Operate on these elements according to the operator, and push the result back to the Stack
Step 4: Step 2 and 3 will be repeated until the end has reached.
Step 5: The Result is stored at the top of the Stack, return it
Step 6: End
Complexity of Prefix evaluation
The Prefix evaluation algorithm has linear complexity O(N). Since we scan the expression once and perform push and pop operations which take constant time.