Problem B
Dijkstra Two Stack
Mathematical expressions can be evaluated with Dijkstra’s Two-Stack Algorithm, thus beginning to bridge the wide gap between mathematicians and programmers. However, being the programming purist that you are, you would never write an expression like “$4 + 6^2$” when what you really mean is add(4, sqr(6)). You have decided to adapt Dijkstra’s Two-Stack algorithm to evaluate expressions like you write them!
You have the following function signatures in your repertoire:
|
int add(int x, int y) |
|
||
|
int sqr(int x) |
|
||
|
int min(int x, int y, int z) |
|
In an attempt to avoid pesky overflow issues, you have decided that all functions in your repertoire return their answers modulo $1\, 000\, 000\, 007$.
Input
The first and only line of the input consists of the expression you want to solve. It contains at most $100\, 000$ function calls. You may assume all integers in the input are non-negative. For simplicity you may also assume that there are added spaces between each of the tokens in the input (see samples).
Feel free to use the code at https://algs4.cs.princeton.edu/13stacks/Evaluate.java.html as a starting point if you want.
Output
Output a single integer, the integer value represented by the expression.
| Sample Input 1 | Sample Output 1 |
|---|---|
add ( 4 , sqr ( 6 ) ) |
40 |
| Sample Input 2 | Sample Output 2 |
|---|---|
min ( add ( 1000000000 , 7 ) , sqr ( sqr ( 2 ) ) , 1 )
|
0 |
