Detailed Example
| operator | precedence | associativity |
|---|---|---|
| ^ | 4 | Right |
| * | 3 | Left |
| / | 3 | Left |
| + | 2 | Left |
| - | 2 | Left |
| Token | Action | Output (in RPN) | Operator Stack | Notes |
|---|---|---|---|---|
| 3 | Add token to output | 3 | ||
| + | Push token to stack | 3 | + | |
| 4 | Add token to output | 3 4 | + | |
| * | Push token to stack | 3 4 | * + | * has higher precedence than + |
| 2 | Add token to output | 3 4 2 | * + | |
| / | Pop stack to output | 3 4 2 * | + | / and * have same precedence |
| Push token to stack | 3 4 2 * | / + | / has higher precedence than + | |
| ( | Push token to stack | 3 4 2 * | ( / + | |
| 1 | Add token to output | 3 4 2 * 1 | ( / + | |
| − | Push token to stack | 3 4 2 * 1 | − ( / + | |
| 5 | Add token to output | 3 4 2 * 1 5 | − ( / + | |
| ) | Pop stack to output | 3 4 2 * 1 5 − | ( / + | Repeated until "(" found |
| Pop stack | 3 4 2 * 1 5 − | / + | Discard matching parenthesis | |
| ^ | Push token to stack | 3 4 2 * 1 5 − | ^ / + | ^ has higher precedence than / |
| 2 | Add token to output | 3 4 2 * 1 5 − 2 | ^ / + | |
| ^ | Push token to stack | 3 4 2 * 1 5 − 2 | ^ ^ / + | ^ is evaluated right-to-left |
| 3 | Add token to output | 3 4 2 * 1 5 − 2 3 | ^ ^ / + | |
| end | Pop entire stack to output | 3 4 2 * 1 5 − 2 3 ^ ^ / + |
If one was writing an interpreter, this output would be tokenized and written to a compiled file to be later interpreted. Conversion from infix to RPN can also allow for easier simplification of expressions. To do this, act like one is solving the RPN expression, however, whenever one come to a variable its value is null, and whenever an operator has a null value, it and its parameters are written to the output (this is a simplification, problems arise when the parameters are operators). When an operator has no null parameters its value can simply be written to the output. This method obviously doesn't include all the simplifications possible: It's more of a constant folding optimization.
Read more about this topic: Shunting-yard Algorithm
Famous quotes containing the word detailed:
“Modern tourist guides have helped raised tourist expectations. And they have provided the natives—from Kaiser Wilhelm down to the villagers of Chichacestenango—with a detailed and itemized list of what is expected of them and when. These are the up-to- date scripts for actors on the tourists’ stage.”
—Daniel J. Boorstin (b. 1914)
“... every event has had its cause, and nothing, not the least wind that blows, is accident or causeless. To understand what happens now one must find the cause, which may be very long ago in its beginning, but is surely there, and therefore a knowledge of history as detailed as possible is essential if we are to comprehend the past and be prepared for the future.”
—Pearl S. Buck (1892–1973)