CS2092D-ASSIGNMENT 6 Solved

QUESTIONS

 

3. Write a program for converting a given infix expression to postfix form using a 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-d)

Sample Output 1: abcd-*+

Sample Input 2:

a*(c+d)/(e+f*g-k*p)

Sample Output 2: acd+*efg*+kp*-/

4.    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 children 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 ‘t’ 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 operators +,−,∗, and /.

•   Character ‘i’ is to perform inorder traversal of expression tree T by calling the function Inorder(T).

•   Character ‘p’ is to perform preorder traversal of expression tree T by calling the function Preorder(T).

•   Character ‘s’ is to perform postorder traversal of expression tree T by calling the function Postorder(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 the expression tree.

•   For option ‘p’, print the expression obtained from preorder traversal of the expression tree.

•   For option ‘s’, print the expression obtained from postorder traversal of the expression tree.

Sample Input e ab+cd-*

i

p

s t

Sample Output a+b*c-d *+ab-cd ab+cd-*

5.    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 a 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:

9      2 1 * + 9 - 4 *

Sample Output 1:

8

Sample Input: 2

10  7 3 2 + * - 7 2 * +

Sample Output 2:

-11