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)
“... 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)