shunting yard algorithm
To convert from standard infix notation to reverse Polish notation
, the Dutch computer programmer Edsger Dijkstra came up with the shunting yard algorithm.
Given a string of tokens, a token reader that ignores whitespace (except to delimit numbers), a number stack, an operator stack and an output queue execute the following steps:
1. Read the tokens in order until end of line. Put number tokens on the output queue. Put operator tokens on the operator stack: if an operator is associative, and has lesser precedence than the operator below it on the operator stack, pop the lower operator off the operator stack and put it on the output queue. If the operator is a left parenthesis, push it onto the operator stack. If the operator is a right parenthesis, start popping operators off the operator stack and onto the output queue until a left parenthesis is encountered. If no left parenthesis is found, throw a mismatched parenthesis exception. 2. At end of line, pop all operators off the operator stack and onto the output queue. If a left parenthesis is encountered during this process, throw a mismatched parenthesis exception. 3. Send the contents of the output queue to the appropriate output device.
What the mismatched parenthesis exception does depends on the device. In the case of a palm calculator, the exception might just turn on the error ”E” and ignore input until the error clear key is pressed. In the case of a calculator implemented on a computer, the exception could give an appropriate message and ask the user to try again.
| Title | shunting yard algorithm |
|---|---|
| Canonical name | ShuntingYardAlgorithm |
| Date of creation | 2013-03-22 16:10:16 |
| Last modified on | 2013-03-22 16:10:16 |
| Owner | Mravinci (12996) |
| Last modified by | Mravinci (12996) |
| Numerical id | 4 |
| Author | Mravinci (12996) |
| Entry type | Algorithm |
| Classification | msc 68N17 |
| Classification | msc 03B70 |