CS240 Project 1
Simple Calculator
Wed. 09/23/2009 9:30PM
Please Start Early!!!
Write a calculator which supports expressions containing non-negative real numbers as operands and "+,-,*,/,(,)" as operators.
There are two parts to this implementation. In the first part, an "infix" expression must be converted to "postfix" (or Reverse Polish) form. In the second part, the expression in postfix form is evaluated, so that the calculator can output the result.
As in C Language, in expressions containing "+,-,*,/", operators "*,/"
have higher precedence while "+,-"
have lower precedence. When two operators have the same precedence, they're
evaluated from left to right (Left Associative). Paired parentheses "(
)" increase the precedence of the operators inside the parentheses, and
such parentheses can be nested. So the innermost nested operators will have the
highest precedence. For example: 2.5-0.5*(4.3+3.7)=-1.5, where +
is evaluated first. This is an example of an infix expression, i.e., infix
because an operator appears between the operands it is applied to.
An expression must be converted into Reverse Polish notation before
evaluation. Reverse Polish notation is another name for a postfix expression,
i.e., postfix because operators appear after operands (reading left to right)
they must be applied to. When we normally write arithmetic expressions we use
infix notation, and because infix notation can be ambiguous without
parentheses, we are forced to use parentheses to remove all ambiguity in
evaluation. Reverse Polish notation (postfix), on the other hand, may not look
normal to us at first glance, but they have an important advantage --- we can
evaluate them without ambiguity even without parentheses. This is why computers
like to have expressions presented in this form.
For example, the infix expression "2.5-0.5*(4.3+3.7)" becomes "2.5 0.5 4.3 3.7 + * -" in postfix (Reverse Polish) form; similarly, infix "1+(3+5*2)*(4-2)" becomes "1 3 5 2 * + 4 2 - * +" in postfix.
We now know that our calculator can evaluate an expression only if it is able to see the expression in postfix form. But how does it do the evaluation?
To evaluate Reverse Polish expression, a data structure called "Stack" is used.
We will implement a Stack as a simple array, with two
operations: Pop and Push. Push adds an item to the top of the Stack (array) and
Pop removes an item from the top of the Stack (array), so that a Stack
operates in "Last in, First out" (also called LIFO) mode. For us,
items will be the operands (i.e., numbers) in each postfix expression. An
integer s_top is used to point to the top of
the stack, i.e., the place in the array where the most recently Pushed item is
stored.
When the Stack is empty, s_top = -1 because no array
space is being used. When the first item is Pushed onto the stack, s_top = 0 because array[0] will
hold that element. When three elements are on the stack, array[0], array[1] and
array[2] are in use; now s_top = 2, indicating that
array[2] is the top of the stack. Thus (s_top+1) serves as the current size of
the stack.
Suppose our operations are: Push(3),
Push(6), Push(8) (sequentially). The array will contain (3,6,8),
where 3 is at the bottom of the stack, 8 is at the top of the stack, and s_top = 2. If we now execute a Pop()
operation, 8 is returned as result and 6 becomes the top of the stack, with s_top = 1.
Given a stack, we can use the following
rules to evaluate a postfix expression.
Read the expression from left to right. If we meet an operand (i.e., number),
Push it onto the stack. If we meet an operator (all operators in this lab are
binary), Pop two operands from the stack and perform the calculation defined by
the operator (e.g., if it's a * then do a multiplication) on the two operands,
and Push the result (an operand) back onto stack. Each time such an evaluation
is done, the result is pushed onto the stack and may
become an operand for the next operator you read. When you are done, the stack
will contain only one number, which is the result operand of the entire
evaluation.
Example: to evaluate "3 5 + 4 2 - *", first
Push 3 and then 5 onto the stack. Next we read a '+' which cause two Pops of
the stack. The two numbers Popped are added and the result 8 is Pushed back onto the stack. Now the stack only contains the
number 8. Next, two Pushes are made when we read 4 and 2. When '-' is read,
both 4 and 2 are Popped, the operation 4 - 2 is
performed. The result of 2 is Pushed onto the stack.
Finally, when the * is read, the operands 8 and 2 are Popped and the result of
16 is Pushed onto the stack. Since there are no more operators, we know that
the single operand 16 on the stack is the result of the evaluation.
We know how to evaluate a postfix
expression. But how do we get from infix to postfix in the first place?
A simple algorithm can accomplish this, with the help of two stacks (a result
stack and an operator stack).
As the expression is read, use the following steps:
1. When a number is met, push it onto the result stack.
2.When an operator is met
(a) If the operator stack is empty, push it onto the
operator stack.
(b) Else, sequentially pop operators off the operator stack
provided they have a higher precedence, pushing them onto the result stack as
they are popped off. Now the operator stack is ready for the current
operator to be pushed onto it, so perform this push operation.
This step guarantees that any operator in the operator stack has higher
precedence than those operators below it in the stack.
3. When the entire expression has been scanned, pop each operator still in the
operator stack off the operator stack and push it (sequentially) onto the
result stack.
Example: We want to convert "2.5-0.5*(4.3+3.7)" to postfix form:
1. Push 2.5 onto result stack and '-' onto operator stack.
2. Push 0.5 onto result stack and '*' onto operator stack (Because '*" has
higher precedence than '-' nothing is popped).
3. Push 4.3 onto result stack and '+' onto operator stack. (Because '+"
within parenthesis has higher precedence)
4. Push 3.7 onto result stack. Now the whole expression has been read.
5. Pop all the elements off operator stack and push them onto result stack.
The result stack becomes 2.5 0.5 4.3
3.7 + * - which is the desired expression.
Here is another example to convert "1+(3+5*2)*(4-2)"
1. 1 is pushed onto result stack and '+' is pushed onto operator stack.
2. 3 is pushed onto result stack and '+' is pushed onto operator stack.
3. 5 is pushed onto result stack and '*' is pushed onto operator stack.
4. 2 is pushed onto result stack.
5. The '*' is outside the parentheses, which means has a lower precedence than
the previous two operators which are in the operator stack. So the previous '*'
and '+' are popped and pushed onto result stack. Then the new '*' is pushed
onto operator stack.
6. 4 is pushed onto result stack and '-' is pushed onto operator stack.
7. 2 is pushed onto result stack and all the remaining
elements in operator stack are popped and pushed onto result stack.
The result stack is "1 3 5 2 * + 4 2 - * +", which is the desired
postfix expression; and you already know how to evaluate it.
When the Calculator is executed, the program
first display a welcome message and then wait for the input from user.
The user can input an expression. If the expression is valid, the correct answer
will be given. Else, "Invalid Expression"
message is displayed for illegal input. So you must check for valid inputs ---
a key requirement in
defensive programming, so that your program need never be "surprised"
by the unexpected.
After that, the calculator waits for the next expression input from the user.
If the user inputs "quit", then the program terminates.
Valid expression means the expression only contains '0'-'9', '.' and
'+','-','*','/','(',')' characters with a newline '\n' at the end of it. Any
other characters (including space) are illegal. Also, the expression should be
evaluable (no unpaired parenthesis, no operand missing, ....).
The result should be printed out in the precision of the sixth digit after the
decimal point.
You can assume the length of the input expression is always less than 300
characters. The calculator only supports non-negative real numbers as operands.
So 2*(-1) is not allowed while 2*(0-1) is OK.
%proj1.out
Welcome to My Calculator
6+4*2
Answer: 14.000000
5.64-9.884*2.5/(4-(3+2)*(4.22-1))
Answer: 7.682149
5.64-0.22+3*
Invalid Expression
0-2*4+5*(6-2))
Invalid Expression
2+ 3
Invalid Expression
2+3*5+(5+(5+2*3/(4-2)))
Answer: 30.000000
2+(5*(44-(5-4*6-5.5)/(4.11-6)))
Answer: 157.185185
(5*2)(3+4)
Invalid Expression
3.55.4+2
Invalid Expression
quit
Goodbye
(for convenience, you can download the sample input
file here and use "project1.out<input.txt"
to test your program.)
The use of Reverse Polish also makes it easy to check the validity of the expression. When evaluating the Reverse Polish, if at last, the stack doesn't contain exactly 1 element as the result, then the original expression must be illegal. Also, when we perform a binary operation and haven't enough elements in the stack to pop (2 for binary), the original expression also must be wrong.
Because "( )" is allowed in the expression, you
probably need a variable to store the current parenthesis layer when you scan
the expression to convert it to reverse polish. If we define that any sub
expressions outside any parenthesis has the layer of 0 and each '(' increase
the layer by 1 and ')' decrease the layer by 1, then the expression is invalid
if the layer becomes negative during the conversion or the layer isn't 0 at the
end of the conversion.
Dont forget the library function atof can convert a string to a real number.
You can use any standard library functions EXCEPT scanf(). No other library or function is allowed.
Any cheating behavior (copy code from Internet or from
other students) will be severely dealt with according to departmental and
University policy, with a report to the Dean of Students. All of your codes
will be analyzed automatically to find potential cheating.
When you are satisfied that your program works correctly (or you run out of time), please do the following.
turnin -c cs240=XXXX -p project1 project1
where XXXX represents your lab section number.
The turnin
section is as follows:
|
Section |
Time |
TA |
|
0201 |
Thursday 15:30-17:20 |
Dan Zhang |
|
0301 |
Friday 09:30-11:20 |
Suli Xi |
|
0401 |
Friday 13:30-15:20 |
Youhan Fang |
|
0501 |
Thursday 09:30-11:20 |
J. C. Chin |
Make sure turnin reports that your project was submitted for grading. You can check the files you have submitted by running the following command:
turnin -c cs240=XXXX -v -p project1
|
Makefile |
5 |
|
Program terminates successfully when the input is "quit" |
5 |
|
15 test cases |
90 (6 for each) |
Notice: NO Partial Credit will be given in this project. If your program fails to pass 1 test case, you lose all the points of that case.