CS2092D Assignment #8 Solution

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