Infix, Prefix and Postfix Notation
There is three main forms of represent a math expression in literature:
The usual way we use to write expressions. There is four basic operator +,-,* and / with predefined precedence and parenthesis to enforce an arbitrary evaluation order. Parenthesis have the most high precedence over * and / with same precedence, + and - have the lowest precedence.
Example:
(1 + 2) * (4 - 3) / 2 + 4
(3) * (4 - 3) / 2 + 4
3 * (4 - 3) / 2 + 4
3 * (1) / 2 + 4
3 * 1 / 2 + 4
3 / 2 + 4
1.5 + 4
5.5
Operator are written before their operands, like infix there is two operands for each operation.
Operator are written after their operands, very easy to be calculate using a stack.
Infix notation is very common to person daily work, but require is not so simple implementation to handle it. A option is convert from infix to postfix to gain all benefits of simple syntax o postfix notation.
This algorithm require a stack to store operator and a fifo list to store the output postfix notation output.
- When is an operand, add to output.
- When is an operator and stack is empty, push on stack.
- When is an operator and element of top of stack has lower precedence, push operator on stack
- When is an operator and element on top has higher or equal precedence, pop stack to output and push operator on stack
- When found (, popup stack to output until found correspondent )
Notes: ( has higher precedence of all when is read from input, but lower of all when on stack
(300 + 23) * (43 - 21) / (84 + 7)
input: (300 + 23) * (43 - 21) / (84 + 7)
stack:
output:
input: 300 + 23) * (43 - 21) / (84 + 7)
stack: (
output:
input: + 23) * (43 - 21) / (84 + 7)
stack: (
output: 300
input: + 23) * (43 - 21) / (84 + 7)
stack: (
output: 300
input: 23) * (43 - 21) / (84 + 7)
stack: ( +
output: 300
input: ) * (43 - 21) / (84 + 7)
stack: ( +
output: 300 23
input: * (43 - 21) / (84 + 7)
stack:
output: 300 23 +
input: (43 - 21) / (84 + 7)
stack: *
output: 300 23 +
input: 43 - 21) / (84 + 7)
stack: * (
output: 300 23 +
input: - 21) / (84 + 7)
stack: * (
output: 300 23 + 43
input: 21) / (84 + 7)
stack: * ( -
output: 300 23 + 43
input: ) / (84 + 7)
stack: * ( -
output: 300 23 + 43 21
input: / (84 + 7)
stack: *
output: 300 23 + 43 21 -
input: (84 + 7)
stack: /
output: 300 23 + 43 21 - *
input: 84 + 7)
stack: / (
output: 300 23 + 43 21 - *
input: + 7)
stack: / (
output: 300 23 + 43 21 - * 84
input: 7)
stack: / ( +
output: 300 23 + 43 21 - * 84
input: )
stack: / ( +
output: 300 23 + 43 21 - * 84 7
input:
stack: /
output: 300 23 + 43 21 - * 84 7 +
input:
stack:
output: 300 23 + 43 21 - * 84 7 + /