Desk Calculator

BIRLA INSTITUTE OF TECHNOLOGY & SCIENCE, PILANI
WORK INTEGRATED LEARNING PROGRAMMES DIVISION
BITS-WIPRO Collaborative Programme: MS in Information Technology, YEAR-2012.

Abstract: The project is to solve an infix expression using a desk calculator. Input is given as an infix expression and output is obtained in a text file. Method followed to solve the expression is, the input is fetched from the input text document and converted to postfix notation using expression tree data structure, the resulted RPN expression is evaluated and the result is shown in output text file. Infix is converted to postfix because, it is easy for the compiler to execute the expression in postfix format. Commonly used data structures for evaluating expressions are stacks and expression trees, both of the above data structures are analyzed and concluded that expression trees are the best suited data structure for solving infix expression.

1.Introduction:

Consider a situation where you are writing a programmable calculator. If the user types in 10 + 10, how would you compute a result of the expression? You might have a solution for this simple expression. But what if he types in 3 * 2 / (5 + 45) % 10 ? What would you do then?

The expression that you see above is known as Infix Notation. It is a convention which humans are familiar with and is easier to read. But for a computer, calculating the result from an expression in this form is difficult. Hence the need arises to find another suitable system for representing arithmetic expressions which can be easily processed by computing systems. The Prefix and Postfix Notations make the evaluation procedure really simple. The calculator you will be working with uses Reverse Polish Notation (RPN), which avoids the ambiguities that can be caused by operator precedence and parentheses, but requires the calculator to remember many operands. RPN is just another name for postfix notation

This means that our program would have to have two separate functions, 1) To convert the infix expression to postfix or RPN. 2) To evaluate the postfix expression.
We first introducing, to the conversion techniques first and later move on to writing the expression evaluator functions. Let us first introduce ourselves to the infix and postfix notations.

1.1 Infix and Postfix

We use infix notation for representing mathematical operations or for manually performing calculations, since it is easier to read and comprehend. But for computers to perform quick calculations, they must work on prefix or postfix expressions.

1.1.1 BODMAS Rule Now let's take a expression : A + B / C For this we need to use the BODMAS rule. This rule states that each operator has its own priority and the operators with the highest priority are evaluated first. The operator priority in descending order is BODMAS which is:

B O D M A S
Bracket Open -> Division -> Multiplication -> Addition -> Subtraction

Hence, in the preceding example, B / C is evaluated first and the result is added to A.

1.2 Infix to Postfix Conversion: To convert A + B / C into postfix, we convert one operation at a time. The operators with maximum priority are converted first followed by those which are placed lower in the order. Hence, A + B / C can be converted into postfix in just X steps.

1. A + B / C (First Convert B / C -> B C /)
2. A + B C / (Next Operation is A + (BC/) -> A BC/ +
3. A B C / + (Resultant Postfix Form)

Sometimes, an expression contains parenthesis like this: A + B * ( C + D ) Parenthesis are used to force a given priority to the expression that it encloses. In this case, C+D is calculated first, then multiplied to B and the added to A. Without the parenthesis, B * C would have been evaluated first. To convert an expression with parenthesis, we first convert all expressions that are enclosed within the simple brackets like this:
[INFIX TO POSTFIX]
:: A + B * ( C + D )
1: A + B * C D +
2: A + B C D + *
3: A B C D + * +

Once an expression has been converted into postfix or prefix, there is no need to include the parenthesis since the priority of operations is already taken care of in the final expression.

2. Software and Hardware Requirements:
2.1 Hardware Requirements:
Processor : 32 bit
RAM : 2 GB
Hard Disk : 80 GB
Desktop screen : 15.4”

2.2 Software Requirements:
Language : Turbo C
Operating system : Windows

3. Literature Review Solving a simple arithmetic calculation using calculator with two operands is simple, but the same with large infix expression contains of parenthesis, operators and operands are bit difficult. As per our analysis, evaluating a large infix expression is not much complex with a proper data structure. As a result we found that stack and expression trees are the best data structure for the implementation of a calculator to solve a infix expression. Solving a infix expression in a calculator follows 2 major steps, one to convert the infix to postfix notation and another to evaluate the postfix expression. Directly solving an infix expression using a calculator is difficult. The calculator deals with postfix notation avoid the ambiguities that can be caused by operator precedence and parentheses. Implementation of this expression evaluating calculator with stack data structure is planned to construct with a effective dynamic data structure called as link list Therefore it is concluded that, implementation of this desk calculator using stack with link list implementation is the best one and it also reduces the complexity of implementation.

4. Software Requirement Analysis
4.1 Problem statement: Construct a calculator to accept an infix expression from a text document, which at least includes { (, ), +, -, *, /, %, and ^ } . If entered infix expression is valid then process the expression and print the result in a output text document, else show an error as invalid expression.
4.1.1 Input format Input format is in infix notation format 1) 3+2-(3/2)*89 2) 8+79(9*7- 8
4.1.2 Output format Output of the above example is 1) -128.5 2) ERROR IN INFIX NOTATION
4.2 Modules Evaluating an infix expression in calculator comprises of four functional blocks, they are 1) Read Infix expression from input text document. 2) Conversion of infix to postfix expression. 3) Evaluating postfix expression. 4) Print the result back in the output text document.

4.3 Description of Functional Blocks
4.3.1 Reading Input From Input Text Document Input file has infix expressions, each line contains a expression. Those expressions are read from the text document one by one using a file pointer. Input is read one by one till the end of file.
4.3.2 Conversion of Infix To Postfix Form For converting an infix expression to postfix, stack is used with link list implementation, the conversion technique is explained below. 1) Scan the infix expression. 2) If an operand is encountered, add it to the postfix expression. 3) If an operator is encountered and the stack is empty, push it onto the stack. 4) If an operator is encountered and stack is not empty then compare the operator with the operator in the stack * If the recently encountered operator is of “<” precedence than the one in stack, then pop operators one by one from stack till that meets “<=” precedence and append to postfix expression. * If the recently encountered operator has higher precedence then push the recently encountered operator onto the stack. 5) If a open ‘(‘parenthesis is encountered, push that to stack. 6) If a closed ‘)’ parenthesis is encountered, pop the stack one by one till ‘(‘.

Eg: In figure 1.1 ,A trace of the algorithm that converts the infix expression a - (b + c * d) / e to postfix form

4.3.3 Evaluating Postfix Expression Resulted postfix expression does not contain parenthesis, hence there is no need to worry about precedence, and the evaluating technique used is explained below 1) Scan for the given postfix expression from left to right, one element at a time. 2) Check whether it is an operand or an operator. 3) If it is an operand the n push the element in to stack and if it is an operator then pop the two elements from the stack. Apply the given operator on them and then push back the returned result in to the stack 4) Repeat the step 1 to 3 until the whole postfix expression comes to the end. 5) Pop the element from the stack which should be the only element in the stack and return it from the function as the result of the expression.
E.g.: In figure 1.2 the action of a postfix calculator when evaluating the expression 2 * (3 + 4)

4.3.4 Printing Result Back In Output Text File Finally evaluated result is written back into the output text file. Output of each expression is written line by line in same order. Evaluated result or error statement is written in the output file.

5. Software Design
5.1 Use Case Diagram

Fig 1.3 use case diagram for a calculator

5.1.1 Use Case Summaries

1) Enter Operand: The user enters an operand and it is stored on the stack where it will be operated on later.
2) Create a Polynomial. The user creates a polynomial from a sequence of numbers representing coefficients and exponents.
3) Operate. The user performs some operation on operands previously entered into the calculator.

5.2 Sequence Diagrams This shows the sequence diagram for the two types of simple operations that a user can perform. Since any complex operations are combinations of simple ones in this project, This can be extended for most uses.

Fig 1.4 Sequence diagram for a calculator

5.3 Functional Diagram

Fig 1.5 Functional diagram for a calculator

7. Testing

7.1 White Box Testing Scenarios

Modules | Scenario | Input | Output | Status | Conversion | To verify the functionality, whether it is possible to convert a infix expression to a correct postfix format. | 3+5*7-8 | 357*8-+ | Pass | Evaluation | To verify the functionality of evaluating a postfix expression | 357*8-+ | 30 | Pass | Conversion | To verify the functionality, whether it is possibleto return an error by conversion block, if the input is wrong. | 5+8*(6-7 | Returns error | Pass |

Table 1.1 for white box testing

7.2 Black Box Testing Scenarios For A Desk Calculator

Scenario | Input | Output | Status | To verify the functionality, whether it is possible calculate an infix expression (+ve scenario) | 3+5*7-8 | 30 | Pass | To verify negative case scenarios like , entering an invalid expression | 5+8*(6-7 | ERROR IN INFIX EXPRESSION | Pass | Testing one more negative case scenario | (9*7-)+8 | ERROR IN INFIX EXPRESSION | Pass |

Table 1.2 for black box testing

9. References

[1] B. B. Welch. Practical Programming in Tcl and Tk, 3rd ed. 2000.

[2] J. Zelle. Python Programming: An Introduction to Computer Science. 2004.

[3] http://cplusplus.com/reference/stl/stack/

[4] http://www.drdobbs.com/184401948 - UML for C programming.