CS3401 HW 7

package trees;
/** Course: CS 3401

 * Section: 01

 * Name: Dalibor Labudovic

 * Professor: Prof. Shaw

 * Assignment #: Homework #7

 */

 import java.math.BigDecimal;
import java.util.*;

//********************************************************************
//

Evaluates a given expression by first converting it to a
// Postfix Stack and then to an Expression Tree and then
// evaluating the Expression Tree
//********************************************************************

 public class EvaluateExpressionTree {

 public static void main(String[] args) {

 Scanner input = new Scanner(System.in);

 System.out.println("Enter an equation in infix notation: " + "[Ex: 10+6/3 ]");

 String expression = input.nextLine();

 input.close();

 try {

 System.out.println("Result = " + evaluateExpressionTree(expression).stripTrailingZeros().toPlainString());

 }

 catch (Exception ex) {

 System.out.println("Bad expression");

 }

 }

 // Converts an expression String into an expresstion Tree
  //   and evaluates it and returns the answer as a BigDecimal

 public static BigDecimal evaluateExpressionTree(String expression) {

 // Create a postfix operandStack of the expression

String
    Stack pStack = new ConvertExpression(expression).
                                                    
getPostfixStack();
// Convert the postfix stack to a an expression tree 
ExpressionTree tree = convertTree(pStack);

// Evaluate the expression tree
                return evaluateExpressionTree(tree);
 } 
// Takes a postfix stack of strings and returns an ExpressionTree  

public static ExpressionTree convertTree(Stack stack) {
 
if (stack.isEmpty())  return null;  
String token = stack.pop(); 
if (isOp(token)) {  // Token is an operato so make a subtree  ExpressionTree rightTree = convertTree(stack); ExpressionTree leftTree = convertTree(stack); return new ExpressionTree(token,leftTree,rightTree); } else // Token is an operand, so make a leaf node  return new ExpressionTree(token); }  // Takes an ExpressionTree and evalutates it and returns a BigDecimal  public static BigDecimal evaluateExpressionTree(ExpressionTree tree) {  if (tree == null || tree.isEmpty())
       return null; String token = tree.getRootElement();  if (isOp(token))  { // Token is an operator
    BigDecimal b = evaluateExpressionTree(tree.getRightNode()); BigDecimal a = evaluateExpressionTree(tree.getLeftNode());  return doOperation(token,a,b);  } else // Token is an operand
    return new BigDecimal(token);
  } // Takes a token operator and two operands, evaluates them and //returns a BigDecimal  public static BigDecimal doOperation(String token, BigDecimal a, BigDecimal b) { if (token.equals("*")) return(a.multiply(b)); if (token.equals("/"))  return(a.divide(b,12,BigDecimal.ROUND_HALF_UP)); if (token.equals("+"))  return(a.add(b));  return(a.subtract(b)); }

  // Takes a token string and checks if it is an operator  public static boolean isOp(String token) { return token.equals("*") || token.equals("/") || token.equals("+") || token.equals("-");  } }

Popular posts from this blog

CS3401 Practice Quiz 2 Part 2

CS3401 Practice Quiz 2 Part 1