CSC212 Homework 4 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. We use postfix to indicate that the operator appears after (post) the operands. You may want to read this page introducing the concept, or this one, as well.

We, as humans, are used to infix notation. In the infix notation, the operators appear in between the operands. For example 3 + 5. A regular, error-free, infix expression can be transformed into its postfix exquivalent 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.
• The numbers will always be integers
• The operators may be +, -, * or /. 10 2 / results in 5. 10 2 - results in 8.
• 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.

Tip

• To convert a string to an integer, you can use this:

int num = Integer.parseInt( "1234" ); 

• Look up the documentation here.

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:

Postfix expression	Result
3 5 +	8
3 5 + 7 +	15
2 8 + 3 11 + *	140
1 2 3 4 + + +	10
100 3 /	33
5	5

• If you had stored the above expressions in the expressions.txt file, then your program would have output:

8
15
140
10
33
5

Problem #2

• This problem is an extension of Problem #1. Store your program in a file called Hw4_2.java.
• This time we assume that the expressions may have errors in them. Several types of errors are possible:

• The numbers may not be integers, but doubles.
• The postfix notation may not be correct. This can stem from several reasons:

1. Incorrect expressions do not end up evaluating to just one number. For example, the expression "3 5" is incorrect, since it is missing an operator. There would be 2 numbers left in the stack at the end of its evaluation. Similarly, "3 5 6 +" is incorrect.
2. It may be possible to get an operator when the stack contains fewer than 2 numbers at the top. In this case we can't pop 2 numbers to operate on. That would be an error as well.
3. The operation to perform may not result in a valid number (division by 0).

• When your program discovers an error, it should print the word "ERROR" in all-caps, and stop. The error message should contain one word only. No extra spaces.

• Test your program thoroughly and submit it to Moodle.

Problem #3

Sometimes data files contain a large amount of uninteresting or meaningless data.

Imagine, for example, that we are recording the seismic activity in some area. We have a sensor that takes measurements every second and sends a number to a computer. The computer records the value in a text file. The computer system always creates a new file at midnight, and then records all 24*3600=86400 samples in it. In periods of low seismic activity the file contains mostly 0s. When some activity occurs, we may have few values different from 0 recorded in the file.

Your assignment is to write a program that will be given the name of the seismic data file on the command line. For example:

 java Hw4_3  seismic_100214.dat

would be a way to get your program to get the name of the file seismic_100214.dat on the command line. It can then open the file and read all 86400 numbers.

Because we might be running our program on a micro-controller with limited memory, we do not want to store all the 0s in memory. Instead of having a list (vector, array-list, linked-list) containing all the numbers, we keep only the non-0 values. But we want to make sure we also keep the index of the where the values appear in the file.

For example, imagine this series of 20 numbers:

0  0  0  0  0  10  20  -5  23  0  0  0  0  0  0  0  0  0  0  0

Your program would read it and record only the non-zero values, which it would keep in a list of pairs: ( (5,10), (6,20), (7,-5), (8,23) ). The pair (5, 10), for example, indicates that the value 10 appears in Position 5 in the list. We assume that the first number in the file is always at Position 0.