Question

Programming in Java Q: Build an expression tree for a given postfix expression. Then compute the value of the expression by doing an in-order traversal of the expression tree. For example: Your output should print the following: o The input is: "Expression" o The inorder traversal is: "inorder traversal" o The output of the expression is: "output" Please print the output in the same format. (example shown below) The input is: 1 68+ The inorder traversal is: 168 The output of the expression is: 14 REQUIREMENTS: 1) You will incorporate the following java concepts in your program. a) interface b) inheritance with interfaces. 2) You will implement an interface with two functions. (a) build_expression_tree(args) (b) evaluate_expression_tree args) 3) You should use java string split function to parse the given postfix expression into tokens 4) You can use built-in functions like string manipulation functions. You should not use built-in types like Java treeMap, vector, stack, lists etc..

Answer 1

import java.util.Scanner.*;

interface XYZ{

build_expression_tree(args);

evaluate_expression_tree(args);

}

class ExpressionTree implements XYZ{

static boolean isOperand(char c)

{

    return (c >= '0' && c <= '9');

}

static build_expression_tree( char args)

{

    return (int)(c - '0');

}

static int evaluate_expression_tree(String exp)

{

    if (exp.length() == 0) return -1;

    int res = value(exp.charAt(0));

    for (int i = 1; i<exp.length(); i += 2)

    {

        char opr = exp.charAt(i), opd = exp.charAt(i+1);

        if (isOperand(opd) == false) return -1;

        if (opr == '+') res += value(opd);

        else if (opr == '-') res -= value(opd);

        else if (opr == '*') res *= value(opd);

        else if (opr == '/') res /= value(opd);

        else                

return -1;

    }

    return res;

}

public static void main(String args[]){

    String expr1 = "1 6 * 8+";

    int res = evaluate_expression_tree(expr1);

    if(res == -1) System.out.println(expr1+" is Invalid");

    else     System.out.println("Value of "+expr1+" is "+res);

}

}