Assignment • FAQ • Development Guide • Code • Checklist •

HW4 Development Guide

You should use this guide to help you to complete your assignment. You should follow it step by step, resolving errors before going on to the next step. Once you can follow this guide without errors, you should come up with more test cases and compare the output of your program with that of the solution.

Make sure the program compiles with make. You should see some errors about methods not having return statements. Resolve these by adding return statements to the incomplete non-void methods. The program should not run correctly (expect an infinite loop), but it should compile without errors at this point.
Update the HEX debug messages in the LongStack.java that you copied from your homework 3. In particular, in your push, pop, and top methods, you should use the Hex debug to print your item if ithe item has negative value.
Write the method intopost. Follow the algorithm given to you in your Calc.java file. You will have to deal with EOF and blank spaces eventually, but for now, let's ignore error checking and get some basic functionality working. In this homework, other than EOF, spaces, and the newline character, there are three kinds of inputs: numbers, parentheses and operators. You can think of operators as anything that are not numbers, parentheses, EOF, spaces or newlines.
As pointed out in the assignment page, you are going to use MyLib.getchar() and MyLib.ungetc() to implement the algorithm described in the comments in your starter code.

Note: Since you haven't implemented setupword, the priority of operators will not be correct. However, this is okay because you will implement it in later steps.

Hint: When creating stack2, you will be creating a LongStack object like the ones that you have implemented and used in hw3. If you are unclear about how to create a stack, please refere to the provided Driver.java in hw3.

Once you're done, try to run through your intopost in JDB to see if you are getting the correct order.

First open another terminal, (if you are on your local machine, don't forget to ssh into your cs12 account).
Change directory into your hw4/java for both terminals.

In your first terminal, run
$ jdb Main

You should see something printed as \jdb -attach 80[xx] where the [xx] is some arbitrary number.
Copy this line into your second terminal to run the debugger.

main[1] stop in Calc.intopost
main[1] run
…Continue entering next (if need be), until the following message appears in your first terminal (where you entered jdb Main):
Please enter an expression to calculate: 10+20
main[1] next
Continue entering next until you read from System.in into your character variable. Assuming we have a variable 'character' that stores in characters read from standard input. Type the following in your second window:
main[1] print character
character = 49
What this prints out is the ascii value of what is read in (in this case we read in the character '1' from '10' first). Once we confirm we have the right value, let's continue executing code until we reach our digit case.
main[1] next
…Once we are in our digit case (should be a conditional statement), continue to enter next in jdb until we have our value of 10, but right before we push onto the stack. Assuming we store the number we have in a variable 'number', execute this command.
main[1] print number
number = 10
main[1] next
The command above should have executed your push to the first stack, so let's confirm it is there by printing it.
main[1] print stack1.top()
stack1.top() = "10"
Please note that you should never be accessing the stack directly in your code. We are only doing it here for debugging purposes. If you do end up doing this in your code, you will have layer violations because another class is trying to directly access the LongStack without using its methods.
main[1] next
…Continue to enter next until we grab our next character from standard input.
main[1] print character
character = 43
Notice how we see the ascii value. If this is not showing up for you, please make sure you handled the previous case before and make appropriate changes to your code. Once you have confirmed this, continue to enter next until we get to the case in which it is a non-digit (a character that is not between '0' and '9').
main[1] next
…Continue to execute next until you push onto your second stack. Ensure this is the same value as what you had before.
main[1] print stack2.top()
stack2.top() = "43"
Once we have confirmed this, let's set a new breakpoint to the line number that occurs after our main loop ends (the one that processes user input). Then we can see if our first stack has the correct intopost order.
main[1] stop at Calc:<line_number>
Set breakpoint Calc:<line_number>.
main[1] cont
Breakpoint hit: "thread=main", Calc.intopost(), line=<line_number> bci=213
From here on out, let's execute next until we get all of the items from the second stack onto the first stack. We should now be at the line before we jettison our second stack. Let's print out the contents of our first stack.

main[1] print stack1.stackEngine.stack[0]
stack1.stackEngine.stack[0] = 10
main[1] print stack1.stackEngine.stack[1]
stack1.stackEngine.stack[1] = 20
main[1] print stack1.stackEngine.stack[2]
stack1.stackEngine.stack[2] = 43

Once we confirm this, we can enter continue again and see our intopost order printed.
We should now end our program with quit if we are in jdb. The below output evaluates to 0 if we set eval's return to 0 at first.

The expression in postfix order is: 10 20 43
which evaluates to: 0

main[1] quit

When you are done, test your Calc executable with 10+20. You should be expecting

$ ./Calc

Please enter an expression to calculate: 10+20

The expression in postfix order is: 10 20 43
which evaluates to: 0

Please enter an expression to calculate:

Note: To stop your program, input ^C (CTRL+C).
Note: ^D will not work just yet if you have not yet dealt with EOF, which we will do next.
Note: Without the eval method working yet to process the postfix expression, you'll need to only enter one expression per run of your program . If you enter more expressions in the same run of your program, you'll see the numbers and operators add to the postfix expression from the prior expression, which can appear confusing.

From the output above, notice that the + operator is represented by its ASCII value 43. To fix that we will need the method setupword, which we will get to very soon.

Add the conditions for dealing with EOF and spaces in your intopost method. When you are done, run your program again, try evaluating " " (space). You should expect to see the following behavior. Again break in your intopost method. EOF will allow you to handle the ^D option in this step.

To stop your program, input ^D (ctrl-D) when the program is asking for user input. It should work this time and you can either enter type continue or next until it reaches the end of the program.

Next, write the setupword method. Refer to lecture handouts and the FAQ as to how to proceed. Remember to call setupword to process operators and parentheses. When you are done, you should expect operators to be printed correctly.

$ jdb Main
Open another terminal, copy the command and start the debugger like before. In this terminal set a break point in your push method by:
main[1] stop in Calc.setupword
main[1] run
Please enter an expression to calculate: 10 + 20
main[1] next
…repeat until the program gets to return value and print the return value with print option. Does it return the correct value?
main[1] next
…repeat until the program pushes the value into the stack. Which stack the operator is pushed to?
main[1] cont
The expression in postfix order is: 10 20 +
which evaluates to: 0
You should see that now the + operator is printing correctly and this is the result of a correct setupword implementation as well as correct calls to it in your intopost method
Please enter an expression to calculate: ^D

In the above test you should be able to see the difference in the behavior of the program when the character is an operator vs digits. Try to relate the behavior to the notes from class and how it makes sense that we have two stacks to manipulate the digits and operators.

Now let's test it with debug option on as well

$ ./Calc -x

Please enter an expression to calculate: [Stack 2 has been allocated]
10+20
[Stack 1 - Pushing 10]
[Stack 2 - Pushing 0x800000000000022b]
[Stack 1 - Pushing 20]
[Stack 2 - Popping 0x800000000000022b]
[Stack 1 - Pushing 0x800000000000022b]
[Stack 2 has been jettisoned]
The expression in postfix order is: 10 20 +
which evaluates to: 0
expect the evaluated value above to be 0 assuming your eval returns 0.

Please enter an expression to calculate: ^D[Stack 2 has been allocated]
[Stack 2 has been jettisoned]
[Stack 1 has been jettisoned]

Next, let's make sure the priority of your operators is correct. Note that multiplication has a higher priority than addition and should show up before addition within the postfix order.

$ jdb Main
Open another terminal, copy the command and start the debugger like before. In this terminal set a break point in your push method by:
main[1] stop in Calc.intopost
main[1] run
main[1] next
…repeat until the program prompts you for input
Please enter an expression to calculate: 10+20*3
main[1] next
…Continue entering next until we read the multiplication character. We should have this output when printing our character.
main[1] print character
character = 42
main[1] next
…Continue entering next until we reach the operator case in which we will pop from stack2 to stack1 until it's empty or the values have lower priority.
…Let's first confirm we have the correct values on our stack before we pop.
main[1] print stack1.stackEngine.stack[0]
stack1.stackEngine.stack[0] = 10
main[1] print stack1.stackEngine.stack[1]
stack1.stackEngine.stack[1] = 20
…We see that our numbers were correctly pushed onto stack1.
main[1] print stack1.stackEngine.stackPointer
stack1.stackEngine.stackPointer = 1
…We see here that our stack pointer is pointing correctly to 2 because we only have two items on the stack. Now we can go on to print values from stack2 (the operators) using print.
main[1] print stack2.stackEngine.stack[0]
stack2.stackEngine.stack[0] = 0x800000000000022b
…If you are confused why this is the value for '+', I would recommend looking at the FAQ page as there is a nice explanation there.
…Now let's enter next so that we can check the priorities of both of the operators on stack2 ('+') and our current one ('*'). We should see that '*' takes a higher precedence than '+' so we immediately push the multiplication character onto stack2. We should now have both '*' and '+' on stack2. Please confirm this using jdb.
main[1] print stack2.stackEngine.stack[0]
stack2.stackEngine.stack[0] = 0x800000000000022b
main[1] print stack2.stackEngine.stack[1]
stack2.stackEngine.stack[1] = 0x800000000000042a
…If you do not have the correct values for this, then please go back and check to see if you implemented the priority of operators correctly. Keep in mind when you should use top and when you should use pop when checking what is on top of the stack.
Once you have the correct values, we can enter continue to see the below output.
main[1] cont

The expression in postfix order is: 10 20 3 * +
which evaluates to: 0
Note: This evaluates to 0 assuming eval returns 0.

We have successfully implemented priority for this expression but we suggest trying another expression to test the popping functionality for operators such as 10*20+3. In this case, the multiplication operator will get popped from the second stack once we read in the addition operator from standard input.

Next, try an expression using parentheses. Note that the parentheses are gone in the postfix expression.

Write the eval method. The algorithm is given to you in your Calc.java. Once you are done, your evaluations should start making sense.

$ jdb Main
Open another terminal, copy the command and start the debugger like before. In this terminal set a break point in your push method by:
main[1] stop in Calc.eval
main[1] run
Please enter an expression to calculate: ((1+2*3)+5)/6
main[1] next
…repeat until we have found an operand. At this point we should be popping from stack2 to get the operation and then popping from stack1 to get the operands (the numbers). By printing each of these variables and checking the result we get from the 'functions' method from the top of the file, we are able to validate that our individual operations within ((1+2*3)+5)/6 are correct.
main[1] print operation
operation = -9223372036854774742
Note that this value is the hexadecimal 0x800000000000042a printed as a long. This is the word produced in decimal form as a result of your setupword. main[1] print op1
op1 = 3
main[1] print op2
op2 = 2
main[1] print result
result = 6
…after your evaluation, you should be pushing your result onto the first stack. You should confirm that you only have two items in your first stack as of right now. The second item in the stack should be your result.
main[1] print stack1.stackEngine.stackPointer
stack1.stackEngine.stackPointer = 2
main[1] print stack1.stackEngine.stack[1]
stack1.stackEngine.stack[1] = 6
…Continue going through these steps making sure that each time you encounter a number on stack2, you are popping from stack2 and pushing onto stack1. Anytime you encounter an operator, you should be popping from stack2 and getting the correct number of operands from stack1 (remember that one of the methods only needs one operand from stack1). If you are having trouble figuring out which items are operators or numbers, try to think about the difference between numbers and operators on our stacks. What does our setupword do to operators?
Once you confirm that all of these values are correct, you should see this as output:

The expression in postfix order is: 1 2 3 * + 5 + 6 /
which evaluates to: 2

You are almost done! Implement the fact and exponent methods. These methods implement factorial and exponential operations for your calculator. Remember how each one works and translate that behavior into code. Once finished, test your code with the debug flag on so you can see whether your program is taking the proper steps towards calculating the end result. Debug messages are there so they could point the incorrect behavior to the programmer of the code.

./Calc -x
[Stack 1 has been allocated]

[Stack 2 has been allocated]
Please enter an expression to calculate: [Stack 2 has been allocated]
(5!-20)^2
[Stack 2 - Pushing 0x8000000000000028]
[Stack 1 - Pushing 5]
[Stack 2 - Topping 0x8000000000000028]
[Stack 2 - Pushing 0x8000000000000821]
[Stack 2 - Topping 0x8000000000000821]
[Stack 2 - Popping 0x8000000000000821]
[Stack 1 - Pushing 0x8000000000000821]
[Stack 2 - Topping 0x8000000000000028]
[Stack 2 - Pushing 0x800000000000032d]
[Stack 1 - Pushing 20]
[Stack 2 - Popping 0x800000000000032d]
[Stack 1 - Pushing 0x800000000000032d]
[Stack 2 - Popping 0x8000000000000028]
[Stack 2 - Pushing 0x800000000000065e]
[Stack 1 - Pushing 2]
[Stack 2 - Popping 0x800000000000065e]
[Stack 1 - Pushing 0x800000000000065e]
[Stack 2 has been jettisoned]

The expression in postfix order is: 5 ! 20 - 2 ^
which evaluates to: [Stack 2 has been allocated]
[Stack 1 - Popping 0x800000000000065e]
[Stack 2 - Pushing 0x800000000000065e]
[Stack 1 - Popping 2]
[Stack 2 - Pushing 2]
[Stack 1 - Popping 0x800000000000032d]
[Stack 2 - Pushing 0x800000000000032d]
[Stack 1 - Popping 20]
[Stack 2 - Pushing 20]
[Stack 1 - Popping 0x8000000000000821]
[Stack 2 - Pushing 0x8000000000000821]
[Stack 1 - Popping 5]
[Stack 2 - Pushing 5]
[Stack 2 - Topping 5]
[Stack 2 - Popping 5]
[Stack 1 - Pushing 5]
[Stack 2 - Topping 0x8000000000000821]
[Stack 2 - Popping 0x8000000000000821]
[Stack 1 - Popping 5]
[Stack 1 - Pushing 120]
[Stack 2 - Topping 20]
[Stack 2 - Popping 20]
[Stack 1 - Pushing 20]
[Stack 2 - Topping 0x800000000000032d]
[Stack 2 - Popping 0x800000000000032d]
[Stack 1 - Popping 20]
[Stack 1 - Popping 120]
[Stack 1 - Pushing 100]
[Stack 2 - Topping 2]
[Stack 2 - Popping 2]
[Stack 1 - Pushing 2]
[Stack 2 - Topping 0x800000000000065e]
[Stack 2 - Popping 0x800000000000065e]
[Stack 1 - Popping 2]
[Stack 1 - Popping 100]
[Stack 1 - Pushing 10000]
[Stack 2 has been jettisoned]
[Stack 1 - Popping 10000]
10000

Please enter an expression to calculate: ^D

Make sure when your program runs, you don't see any memory errors at the end. You should see the following output:
No memory leaks! All memory has been correctly deallocated.

If you do not see the following output at the end when you exit your Calc with ^D (CTRL+D), go back and debug your code. You most likely forgot to jettison some objects. Tracker should give you an idea of where you most likely forgot to jettison your objects.

At this point, you should test your assignment extensively by coming up with your own test cases. Be sure to test it with and without the "-x" option. To verify that your program behaves correctly, check the output against the solution's output. To run the solution program, type

$ ~/../public/hw4/java/Calc [-x]

Make sure that you have fully commented your program and added method and file headers. Make sure your style follows the Style Outline for CSE 12. Then turn in your program by following The Turnin Procedure.

Note that, in order for your homework to be collected correctly, you must name your file Calc.java and the file must be located in a folder called hw4 in your home directory.

Assignment • FAQ • Development Guide • Code • Checklist •