Description

Department of Computer Science and Engineering
Third Semester B. Tech.(CSE)
CS2092D Programming Laboratory Assignment #8
Policies for Submission and Evaluation:
• Ensure that your programs will compile and execute without errors in the Linux platform.
• Detection of ANY malpractice related to the lab course can lead to awarding an F grade in the course.
Naming Conventions for Submission • Submit a single ZIP (.zip) file (do not submit in any other archived formats like .rar, .tar, .gz).
The name of this file must be
ASSG<NUMBER> <ROLLNO> <FIRST-NAME>.zip
(Example: ASSG1 BxxyyyyCS LAXMAN.zip). DO NOT add any other files (like temporary files, input files, etc.) except your source code, into the zip archive.
• The source codes must be named as
ASSG<NUMBER> <ROLLNO> <FIRST-NAME> <PROGRAM-NUMBER>.c
(For example: ASSG1 BxxyyyyCS LAXMAN 1.c). If you do not conform to the above naming conventions, your submission might not be recognized by our automated tools, and hence will lead to a score of 0 marks for the submission. So, make sure that you follow the naming conventions.
Standard of Conduct
QUESTIONS

1. Write a program for converting a given infix expression to postfix form using STACK. Write a function InfixToPostfix(e) which converts the given infix expression e to postfix expression and returns the postfix expression.
Input format:
The input is an infix expression, with operands represented by characters a to z. Only the binary operators +,−,∗,/ need to be considered.There can be parenthesised subexpressions (including the entire expression). The associativity of the binary operators is from left to right and this would apply to the other questions as well.
Output format:
The output is a postfix expression.
Sample Input 1: a+b*c
Sample Output 1: abc*+
Sample Input 2:
(a+b)*c+d/(e+f*g)-h
Sample Output 2: ab+c*defg*+/+h-
2. Write a program to evaluate a given postfix expression. Write a function EvaluatePostfix(e), that evaluates the given postfix expression e and returns the result of evaluation.
Input format: The input consists of a postfix expression (represented as a characer string), with integer operands and binary operators +,−,∗,/. Operands/operators are separated by space. Assume that only positive operands are present in the expression. Evaluate the postfix expression and print the result.
Output format: The output is the value of expression after evaluation.
Sample Input 1:
2 3 1 * + 9 –
Sample Output 1:
-4
Sample Input: 2
100 200 + 2 / 5 * 7 +
Sample Output 2:
757
3. Write a menu driven program to construct an ExpressionTree T(it is a binary tree in which each internal node corresponds to the operator and each leaf node corresponds to the operand) for a given postfix expression e and perform the tree traversal operations (Inorder, Preorder and Post order) on T. Each node x of T is an object with an attribute data, which is either an operator or an operand of the expression and two pointer attributes: left and right pointing to the left and right child of x respectively. An attribute T.root points to the root node of the tree T. Your program must contain the following functions:
• Main() – repeatedly reads a character ‘e’, ‘i’, ‘p’, ‘s’, or ‘t’ from the terminal and calls the sub-functions appropriately until character ‘e’ is entered.
• Construct-Tree(e) that takes as input a postfix expression e, converts it into an expression tree T and returns a pointer to the root of T.
• Inorder(T) that takes as input an expression tree T and prints the data in the nodes of T in inorder.
• Preorder(T) that takes as input an expression tree T and prints the data in the nodes of T in preorder.
• Postorder(T) that takes as input an expression tree T and prints the data in the nodes of T in postorder.
Input format:
• Each line contains a character from ‘e’, ‘i’, ‘p’, ’t’, ’s’ .
• Character ‘e’ is followed by a postfix expression, which is a combination of characters(operands) from a to z and binary operator +,−,∗,/.
• Character ‘i’ is to perform inorder traversal of expression tree T.
• Character ‘p’ is to perform preorder traversal of expression tree T.
• Character ‘s’ is to perform postorder traversal of expression tree T.
• Character ‘t’ is to terminate the program.
Output Format: • The output (if any) of each command should be printed on a separate line.
• For option ‘i’, print the expression obtained from inorder traversal of expression tree.
• For option ‘p’, print the expression obtained from preorder traversal of expression tree.
• For option ‘s’, print the expression obtained from postorder traversal of expression tree.
Sample Input e ab+cd-*
i
p
t
Sample Output a+b*c-d *+ab-cd ab+cd-*
4. Write a menu driven program for the evaluation of multiple postfix expressions. Input should be read from the file input.txt and output should be written to the file output.txt. Your program should include the following functions.
• Main() reads each line of the file input.txt and calls the function evaluatePostfix(e) until end-of-file is reached.
• evaluatePostfix(e) evaluate the given postfix expression e and print the result.
Input format:
• The input text file consists of multiple lines. Each line contains a postfix expression which is a combination of integers(operands) and symbols(operator) +,−,∗,/ separated by a space. For negative integers, operator 0−0 precedes the integer and no space is provided between 0−0 and the integer. Evaluate the postfix expression and print the result.
Output Format:
• The output (if any) of each command should be printed on a separate line.
Sample Input
2 3 1 * + 9 100 200 + 2 / 5 * 7 +
-20 30 *
Sample Output
-4
757
-600