Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. For example:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Two words are called isomorphic if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all occurrences of it with another letter. The ordering of the letters remains unchanged. No two letters may map to the same letter, but a letter may map to itself.
For example, the words “abca” and “zbxz” are isomorphic because we can map ‘a’ to ‘z’, ‘b’ to ‘b’ and ‘c’ to ‘x’. But “foo” and “bar” are not isomorphic.
We need to define a method which accepts a map & a value, and returns the value’s key in the map.
The Shunting Yard algorithm was developed by Edsger Dijkstra as a means to parse an infix mathematical expression into Reverse Polish notation (postfix).
Here is an step-by-step image for A+B*C-D from wiki.
|A simplified version of the Shunting-yard algorithm (complete version)
- For all the input tokens [S1]:
- Read the next token [S2];
- If token is an operator (x) [S3]:
- While there is an operator (y) at the top of the operators stack and either (x) is
left-associative and its precedence is less or equal to that of (y), or (x) is right-associative
and its precedence is less than (y) [S4]:
- Pop (y) from the stack [S5];
- Add (y) output buffer [S6];
- Push (x) on the stack [S7];
- Else If token is left parenthesis, then push it on the stack [S8];
- Else If token is a right parenthesis [S9]:
- Until the top token (from the stack) is left parenthesis, pop from the stack to the output buffer [S10];
- Also pop the left parenthesis but don’t include it in the output buffer [S11];
- Else add token to output buffer [S12].
- While there are still operator tokens in the stack, pop them to output [S13]
Note: [SN] Relate with code.
Here is a simple implementaion in Java :