Fixed Prefix and Postfix Expressions

Introduction

• Focus on fixed prefix and postfix expressions.
• Evaluation of these expressions as an important application of stacks.
• Definition of expression: Contains constants, variables, symbols, operators, parentheses.

Examples of Expressions

• 5 + 1 - Contains constant and operator.
• P + Q - Contains variables and operator.
• a + 5 - Contains variable and constant with operator.

Binary Operators

• Binary operators need two operands.
• Example: a - 1 + 5
  • For +, operands are 5 and (a - 1).
  • For -, operands are a and 1.
• Expressions are generally written as operand-operator-operand (Infix notation).

Infix Expression Evaluation

• Combine constants, variables, and symbols arranged by grammar rules.
• Evaluation requires precedence and associativity rules.
• Examples:
  • 5 + 1 * 6
    • Output can vary based on evaluation order.
    • Correct evaluation: multiplication before addition (5 + 6 = 11).
  • Parentheses can alter precedence: (5 + 1) * 6 = 36.

Precedence and Associativity Rules

1. Parentheses ( ) - Highest precedence.
2. Exponentiation ^
3. Multiplication * and Division /
4. Addition + and Subtraction -*

• Associativity:
  • Exponentiation: Right-to-left.
  • Other operations: Left-to-right.

Complex Expressions

• Example: 1 + 2 * 3 / 5
  • Multiplication and division same precedence; evaluate left-to-right.
  • Evaluation: 2 * 3 = 6, then 6 / 5, then add 1.
• Example: 2 ^ 2 ^ 3
  • Same precedence; right-to-left evaluation.
  • Correct evaluation: 2 ^ (2 ^ 3) = 256.

Importance of Precedence and Associativity

• Ensures correct parsing and evaluation.
• Avoids incorrect outcomes (e.g., 2 ^ 2 ^ 3 must be evaluated correctly).

Prefix Expressions (Polish Notation)

• Operator precedes operands.
• Infix to Prefix example:
  • a * (b + c) in Infix.
  • Prefix equivalent: * a + b c.

Postfix Expressions (Reverse Polish Notation)

• Operator follows operands.
• Infix to Postfix example:
  • a * (b + c) in Infix.
  • Postfix equivalent: a b c + *.

Advantages of Prefix and Postfix

• No need for precedence or associativity rules.
• Easier for computer parsing (less memory/time consumption).
• Human readability: Infix easier compared to Prefix/Postfix.

Summary

• Three ways to write expressions: Infix, Prefix, Postfix
• Next discussion: Evaluation of Prefix and Postfix expressions with examples.