DS – Expression Evaluation

Expression Evaluation

• An algebraic expression is a legal combination of operands and operators.
• Operand is a quantity (data) on which an operation is performed.
• Operand may be a variable like a, b, c or constants like 1, 2, 3….
• Operator is a symbol.
• Example of an expression x+y*z

Notations: We can represent an expression in different notations.

Infix: Operator surrounded by operands.             X+Y   Prefix: Operator proceeded by operands.             +XY   Postfix: Operator followed by operands.             XY+

Notes:

• Infix notation is seems to be simple but difficult to evaluate.
• We need to consider the priority of operators and associativity of operators.
• Expression 2+3*5 result depends on priority.
• No need to consider these things in the evaluation of Prefix or Postfix expressions.

As there are 3 notations, we have total 6 conversions.

1. Infix -> Postfix
2. Infix -> Prefix
3. Prefix -> Infix
4. Prefix -> Postfix
5. Postfix -> Infix
6. Postfix -> Prefix

• First 2 conversions can be performed using STACK. Hence we called these conversions are applications of STACK.
• Remaining conversions use BST and STACK.