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:
“[The Republicans] offer ... a detailed agenda for national renewal.... [On] reducing illegitimacy ... the state will use ... funds for programs to reduce out-of-wedlock pregnancies, to promote adoption, to establish and operate children’s group homes, to establish and operate residential group homes for unwed mothers, or for any purpose the state deems appropriate. None of the taxpayer funds may be used for abortion services or abortion counseling.”
—Newt Gingrich (b. 1943)
“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)