161 Lab 4 exercises

ssh -x csci fork csci161/lab4 csci161/$USER/lab4
cd csci161
git clone csci:csci161/$USER/lab4
cd lab4

git add dllist.cpp
git add postfix.cpp
git commit -m "...some message describing your changes..."
git push

executable postfix uses files:
• realstack.h and realstack.cpp provide a C++ class for a stack of real numbers
• postfix.h and postfix.cpp provide a program that uses the stack to evaluate postfix expressions
  executable sortlist uses files:
• dllist.h and dllist.cpp provide a C++ class for a doubly-linked list of positive integers
• sortlist.h and sortlist.cpp provide a program that tests the dllist methods

• for postfix you'll be completing the processEntry function in postfix.cpp (and optionally a helper function, applyOp)
• for sortlist you'll be completing all the dllist class methods in dllist.cpp

postfix:
• In postfix expressions (unlike our normal math expressions) we put the values first and the operation last, e.g. to subtract 3 from 5 we would write 3 5 -, or to divide 12 by 4 we would write 4 12 /
• Whenever an operation is encountered it is applied to the two previous values, and the result of the operation replaces the pair of values, thus 4 12 / becomes 3
• When chains of values/operations are given we process them left-to-right, replacing pairs of values when we encounter an operation, e.g. 10 20 30 + * would apply the + to 20 and 30, leaving us with 10 50 *, so the * would then give 500.
  As another example 1 3 - 5 4 * 10 + / would work from left to right:

  1
  1 3
  1 3 - (now replace the 1 and 3 with 3-1, i.e. 2)
  2
  2 5
  2 5 4
  2 5 4 * (now replace the 5 and 4 with 4*5, i.e. 20)
  2 20
  2 20 10
  2 20 10 + (now replace the 20 and 10 with 10+20, i.e. 30)
  2 30
  2 30 / (now replace the 2 and 30 with 30/2, i.e. 15)
  15
  (now we're at the end of the expression so our final result is 15)
  

• The postfix program we're finishing allows the user to enter a postfix expression with a = as the final operator indicating they want to know the result of the expression, e.g. 10 20 30 + * = would give a final result of 500
• If the user has entered a valid expression then whenever we see a +,*,/,- there will be at least two prior values available to work on, and when we reach the = there will be exactly one value left, the final answer. Our program needs to warn the user when their expression is invalid.
  sortlist:
• The program itself in this case is simply meant to test/exercise the various methods of class dllist, a doubly-linked list of positive integers, with methods to insert at the front/back, remove from the front/back, peek at the front/back, lookup the size of the list and whether or not it is empty, and to print the list.
• To do this, the program:
  • asks the user how many values they'll enter
  • reads them in and alternates between inserting at the front and back of the list
  • prints the resulting list
  • asks the user how many values to remove
  • removes and displays them, alternating between removing from the front and back
  • prints the resulting list
  • sorts the remaining list elements (smallest at front, largest at back)
  • prints the final result

sortlist:
• As mentioned above, your task for the sortlist program is to complete all the dllist methods in the dllist.cpp file, adhering to the specifications in dllist.h.
  (Hopefully the implementation is relatively intuitive given the work we've done in lectures on linked lists using just structs and linked lists as a class.)
  postfix:
• For the postfix program, a complete stack class has been provided through realstack.h and .cpp, and our objective is to write code to use the stack to evaluate a postfix expression.
• Much of the helper/support functions have already been written:
  • a getEntry routine to read entries from the user, where each entry is either a positive number or one of + - * / =
  • an isReal function to test if an entry is a positive real number
  • an isOp function to test if an entry is one of + - * / =
  • the main routine to control the entire process
  The student requirement for this portion of the lab is to complete the processEntry function, which does the real evaluation work and some error checking.
  (The framework for another function, applyOp, has been provided which may be useful as a helper function for processEntry.)
• The technique for using a stack to evaluate postfix expressions is as follows:
  • we create an empty stack to hold the real numbers we're working on
  • we read user input one entry at a time
    we call processEntry, passing it the stack and the entry we just read, and let processEntry decide what to do with it
  • processEntry behaves as follows:
    • If the entry is a positive real number then push it on the stack, checking to make sure the push succeeded.
    • If the entry is an = then check to make sure the stack has exactly one value in it (otherwise the user had too few or too many operators in their expression), display that one value and return true to indicate we are now finished with the expression.
    • If the entry is any one of +, -, *, / then it checks to make sure the stack has at least two values (otherwise there have been too many operators for this point in the expression), gets and removes the top two values from the stack (using peek and pop), applies the operator to them, and pushes the result back on the stack. Note that it should check the return value of each peek/pop/push as they're done.
    Note that processEntry returns true when we're done processing the =, false after any other entry (the main routine uses this to decide when it's time to quit).