Difference between revisions of "CSC212 Homework 4 2014"
(→Problem #1) |
(→Problem #1) |
||
| Line 41: | Line 41: | ||
;Example | ;Example | ||
| − | : Assume we want to evaluate the postfix string "3 5 + 6 *". Its ''infix'' equivalent to (3 + 5 ) * 6, which is 48.<br />Here we go: we scan our string, and get each number | + | : Assume we want to evaluate the postfix string "3 5 + 6 *". Its ''infix'' equivalent to (3 + 5 ) * 6, which is 48.<br />Here we go: we scan our string, and get each number, or operator, one at a time. |
3 --> push it in the stack: | 3 --> push it in the stack: | ||
| Line 59: | Line 59: | ||
Done! the result is at the top of the stack. | Done! the result is at the top of the stack. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| + | * You may want to watch this video for an additional example: | ||
| + | <br /> | ||
<center> | <center> | ||
<videoflash>zMDm2MbRG6w</videoflash> | <videoflash>zMDm2MbRG6w</videoflash> | ||
</center> | </center> | ||
| + | <br /> | ||
| + | |||
| + | <br /> | ||
| + | ==Your assignment== | ||
| + | <br /> | ||
| + | * Write a program that reads ''postfix expressions" from the input (there may be several lines of input), and for each one prints out the result. | ||
| + | * Call your program '''Hw4_1.java''', and submit it to Moodle. | ||
| + | * You can assume for this problem that the expressions will '''always''' be error free. | ||
| + | |||
| + | <br /> | ||
| + | ==Testing information== | ||
| + | <br /> | ||
| + | * You may want to put several expressions in a text file, say, '''expressions.txt''', and test your program this way: | ||
| + | |||
| + | javac Hw4_1.java | ||
| + | java Hw4_1 < expressions.txt | ||
| + | |||
| + | * Some expressions and their results: | ||
Revision as of 15:57, 1 October 2014
--D. Thiebaut (talk) 15:49, 1 October 2014 (EDT)
Problem #1
Write a program that computes the result of an arithmetic expression written in reverse polish notation (RPN), also called postfix notation because the operator appears after (post) the operands. You may want to read this page introducing the concept.
A regular, error-free, arithmetic expression can be transformed into its RPN easily, as illustrated with a few examples:
| regular expression | RPN expression |
|---|---|
|
3 + 5 |
3 5 + |
|
3 * ( 5 - 2 ) |
3 5 2 - * |
|
(4 -1 ) * 8 |
4 1 - 8 * |
|
( 5 * 10 ) / ( 3 - 2 ) |
5 10 * 3 2 - / |
RPN expressions can be solved very easily by using a stack. For example, if the expression is:
3 5 + 7 *
which corresponds to (3 + 5) * 7, we proceed as follows: we read the symbols (numbers and operators) one at a time from the input, and if we find a number, we push it in the stack. If we find an operator, we pop 2 numbers from the stack, one after the other, apply the operator to the two numbers, then push the result back in the stack.
- Example
- Assume we want to evaluate the postfix string "3 5 + 6 *". Its infix equivalent to (3 + 5 ) * 6, which is 48.
Here we go: we scan our string, and get each number, or operator, one at a time.
3 --> push it in the stack:
stack = [3]
5 --> push it in the stack:
stack = [5 3] (the top of the stack is 5)
+ --> Operator! we pop the stack, get 5, pop again, get 3, add 5+3 together, 8, push that back in the stack.
stack = [8]
6 --> push it in the stack:
stack = [6 8]
* --> Operator! we pop the stack, get 6, pop again, get 8, multiply 6 by 8 ,48, push that back in the stack.
stack = [48]
Done! the result is at the top of the stack.
- You may want to watch this video for an additional example:
Your assignment
- Write a program that reads postfix expressions" from the input (there may be several lines of input), and for each one prints out the result.
- Call your program Hw4_1.java, and submit it to Moodle.
- You can assume for this problem that the expressions will always be error free.
Testing information
- You may want to put several expressions in a text file, say, expressions.txt, and test your program this way:
javac Hw4_1.java java Hw4_1 < expressions.txt
- Some expressions and their results:
