4.1.3.1 Infix, Postfix, and Prefix Notations; Converting an Infix Expression to Postfix
Computational Structures
In mathematics and computer science, expressions can be written in different notations. The three main notations are infix, postfix, and prefix notations.
- Infix Notation: The operator is placed between the operands. This is the standard notation used in most arithmetic and algebraic expressions. Example: A + B or (A+ B) x C
- In A + B, the operator + is between the operands A and B. Parentheses may be used to clarify the order of operations.
- Postfix Notation (Reverse Polish Notation, RPN): The operator is placed after the operands. This notation does not require parentheses to denote the order of operations. Examples: A + B = AB+ and (A + B) x C = (AB+) x C = AB + Cx
- In AB+, you first encounter the operands A and B, followed by the operator +, indicating that A and B are to be added. In AB + Cx, you first add A and B, then multiply the result to C.
- Prefix Notation (Polish Notation): The operator is placed before the operands. Like postfix notation, prefix notation also does not require parentheses to indicate the order of operations. Example: +AB or +A x BC
- In +AB, the operator + comes before the operands A and B, indicating that A and B are to be added. In +A x BC, you first multiply B and C, then add A to the result.
Converting an Infix Expression to Postfix
Converting an infix expression (like 3 + 4 * 5) to postfix notation (like 3 4 5 *+) can make calculations easier for computers. We use a stack to help with this conversion. Here's a simple explanation: