UCR CS141 

Take Home Assignment 2

Spring Quarter 2003

Prof. Sitanshu Kumar

Assignment:

Project P-2.1 (Text book, Page 136)

Due: One hour before your scheduled lab section time of week April 21 to April 25.

• Overview

The arithmetic expression consists of:

• Numbers. All numbers are integer. 
• Variables. In the format of x1, x2, x3 ......
• Parentheses. They have their usual meaning. Only ( and ) will be used; don't use { } [ ].
• + for addition; used only as a binary operator.
• - for subtraction; used only as a binary operator.
• * for multiplication.
• / for division.

• Input format:

1. Take the input from standard input, and the length of expression is limited to one line.
2. For easy string tokenize of the input expression, separate the operator, operand, and parenthesis by at least one space.
3. All variables are inputted in one line, follow the expression, with the order of x1, x2, x3 ......

For example,

input expression: (  x1  +  2  )  *  4  +  x2  *  (  12  -  x3  /  x4  )

input variables:   3   2   6  3

• Output format:

1. Output the tree in the format you like.
2. Output the prefix expression (preorder traversal of the tree).
3. Output the final value of the expression.

For the above example,

output:

+  *  +  x1  2  4  *  x2  -  12  /  x3  x4

40

• Expression evaluation algorithm

You need two stacks, a operand stack (to hold the numbers and variables), and an operator stack (to hold the operators). Numbers will be int values, operators will be char values.

The algorithm is roughly as follows. Note that no error checking is done explicitly.

1. While there are still tokens to be read in,
   1. Get the next token.
   2. If the token is:
      1. A number: push it onto the operand stack.
      2. A variable: get its value, and push its value onto the operand stack.
      3. A left parenthesis: push it onto the operator stack.
      4. A right parenthesis:
         1. While the thing on top of the operator stack is not a left parenthesis,
            1. Pop the operator from the operator stack.
            2. Pop the operand stack twice, getting two operands.
            3. Apply the operator to the operands, in the correct order.
            4. Push the result onto the operand stack.
         2. Pop the left parenthesis from the operator stack, and discard it.
      5. An operator (call it thisOp):
         1. While the operator stack is not empty, and the top thing on the operator stack has the same or greater precedence as thisOp,
            1. Pop the operator from the operator stack.
            2. Pop the operand stack twice, getting two operands.
            3. Apply the operator to the operands, in the correct order.
            4. Push the result onto the operand stack.
         2. Push thisOp onto the operator stack.
2. While the operator stack is not empty,
   1. Pop the operator from the operator stack.
   2. Pop the operand stack twice, getting two operands.
   3. Apply the operator to the operands, in the correct order.
   4. Push the result onto the operand stack.
3. At this point the operator stack should be empty, and the operand stack should have only one value in it, which is the final result.

• Tree construction:

Create a node for each number, variable, and operator. Store the pointer to the node in the operator stack and operand stack. When applying the operator to the two operands, modify the left pointer and right pointer of the operator node, let them point to the nodes hold the two operands.

Attention:

• Please use the Turn-in System  

1. Put all the files you want to turn-in in one folder
2. Goto:  https://www.cs.ucr.edu/ 
3. Click "student", login using your account name and password
4. Click "WWWTurnin"
5. Choose the class section: "cs141"
6. Specify you turn-in folder name
7. Turn in
   

• Write a Readme plain text file to explain the design of your program and how your program works.

• Include your name, ID, lab section number, email address in  every files you want to turn in.