Could someone take a look at this and perhaps tell me why it isn't working. Node.java and Token.java compile file....it's the Calculator.java that is giving me fits. Thanks in advance, JK.
import java.util.* ;
// class Calculator reads expressions from standard in that may be in postfix,
// prefix, or fully parenthesized infix notation.
// It then creates an expression tree and can create expression strings
// in other notations and/or evaluate the original expression.
public class Calculator
{
private
String postfix, infix, prefix ;
private double value ;
private Node myRoot ;
public static void main(String[] args)
{
System.out.println("This program evaluates fully parenthesized and spaced infix expressions, postfix expressions, and prefix expressions") ;
System.out.println("Enter 'quit' to exit.") ;
// open a console reader
TextReader console = new TextReader(System.in) ;
console.eolIsSignificant(true) ;
// process the console input
VectorQueue tokens = new VectorQueue() ;
while(true)
{
char c = console.peek() ;
if(c=='\n')
{
// end of line, process the expression
console.readChar() ;
if(!tokens.isEmpty())
{
// obtain the first element of the queue
Token firstToken = (Token) tokens.elementAt(0) ;
// check for a quit command
if(firstToken.getType() == Token.OPERATOR &&
firstToken.getOp().equals("quit"))
return ;
// create a new calculator object
Calculator calc = new Calculator(tokens) ;
// print the expression tree to console
System.out.println("Tree:") ;
calc.printTree() ;
// print the expression
System.out.println("Postfix:"+calc.getPostfix()) ;
System.out.println("Prefix:"+calc.getPrefix()) ;
System.out.println("Infix:"+calc.getInfix()) ;
System.out.println("Value:"+calc.getValue()) ;
System.out.println() ;
}
}
else if(c=='(' || c==')')
{
// enqueue a PAREN token
tokens.enqueue(new Token()) ;
console.readChar() ;
}
else if( Character.isDigit(c) )
{
// enqueue a number
tokens.enqueue(new Token(console.readDouble())) ;
}
else if(c==' ')
{
console.readChar() ;
}
else
{
// enqueue a symbol
tokens.enqueue(new Token(console.readWord())) ;
}
}
}
public Calculator(VectorQueue tokens)
{
Token firstToken = (Token) tokens.elementAt(0) ;
// convert this queue into a binary tree by checking the first token
if(firstToken.getType() == Token.PAREN)
buildInfix(tokens) ;
else if(firstToken.getType() == Token.OPERATOR)
buildPrefix(tokens) ;
else
buildPostfix(tokens) ;
// initialize object state
postfix = "" ;
prefix = "" ;
infix = "" ;
value = evaluate(myRoot) ;
}
// getter methods - return object state
public String getPrefix()
{
return prefix ;
}
public String getPostfix()
{
return postfix ;
}
public String getInfix()
{
return infix ;
}
public double getValue()
{
return value ;
}
// printTree prints the expression tree to standard out
public void printTree()
{
printTreeHelp(myRoot, "") ;
}
private void printTreeHelp(Node root, String offset)
{
if(root == null)
return ;
printTreeHelp(root.left, offset + " ") ;
System.out.println(offset + root.data) ;
printTreeHelp(root.right, offset + " ") ;
}
// evaluate recursively traverses the expression tree and in
// doing so builds infix, postfix, and prefix versions of the
// expression and returns the value of the expression
private double evaluate(Node root)
{
if(root.left == null && root.right == null)
{
prefix += " " + root.data ;
postfix += " " + root.data ;
infix += " " + root.data ;
return ((Double)root.data).doubleValue() ;
}
else
{
prefix += " " + root.data ;
infix += " (" ;
double arg1 = evaluate(root.left) ;
infix += " " + root.data ;
double arg2 = evaluate(root.right) ;
postfix += " " + root.data ;
infix += " )" ;
return evaluate((String)root.data, arg1, arg2) ;
}
}
// buildPostfix converts a postfix expression to an expression tree
private void buildPostfix(Queue tokens)
{
Stack stk = new VectorStack() ;
while(!tokens.isEmpty())
{
Token tkn = (Token) tokens.dequeue() ;
if(tkn.getType() == Token.OPERAND)
{
// this token is a number, push it
stk.push(new Node(new Double(tkn.getNum()))) ;
}
else
{
// this token is an operator
// pop the last two elements on the stack
Node arg2 = (Node) stk.pop() ;
Node arg1 = (Node) stk.pop() ;
// create a new node, push it
stk.push(new Node(tkn.getOp(), arg1, arg2)) ;
}
}
myRoot = (Node) stk.pop() ;
}
// buildPrefix converts a prefix expression into an expression tree
private void buildPrefix(Queue tokens)
{
myRoot = buildPrefixHelp(tokens) ;
}
private Node buildPrefixHelp(Queue tokens)
{
Token tkn = (Token) tokens.dequeue() ;
if(tkn.getType() == Token.OPERAND)
{
return new Node(new Double(tkn.getNum())) ;
}
else
{
return new Node(tkn.getOp(), buildPrefixHelp(tokens), buildPrefixHelp(tokens)) ;
}
}
// buildInfix converts an infix expression into an expression tree
private void buildInfix(Queue tokens)
{
myRoot = buildInfixHelp(tokens) ;
}
private Node buildInfixHelp(Queue tokens)
{
Token tkn = (Token) tokens.dequeue() ;
if(tkn.getType() == Token.OPERAND)
{
// this token must correspond to a number
return new Node(new Double(tkn.getNum())) ;
}
else
{
// this is a non-leaf node
Node tmp = new Node() ;
// process the left sub expression
tmp.left = buildInfixHelp(tokens) ;
// next token we encounter is an operator
tmp.data = ((Token)tokens.dequeue()).getOp() ;
// process the right sub expression
tmp.right = buildInfixHelp(tokens) ;
tokens.dequeue() ;
return tmp ;
}
}
private static double evaluate(String operator, double operand1, double operand2)
{
if (operator.equals("+"))
return operand1 + operand2 ;
else if (operator.equals("-"))
return operand1 - operand2 ;
else if (operator.equals("*"))
return operand1 * operand2 ;
else if (operator.equals("/"))
return operand1/operand2 ;
else if (operator.equals("^"))
return Math.pow(operand1, operand2) ;
else
throw new RuntimeException("Illegal operator: " + operator) ;
}
}
==================================================
// class node is a simple implementation of a binary tree node
public class Node {
public Node(Object d) {
this(d, null, null) ;
}
public Node() {
this(null, null, null) ;
}
public Node(Object d, Node l, Node r) {
data = d ;
left = l ;
right = r ;
}
public Node right ;
public Node left ;
public Object data ;
}
===========================================================================
class Token {
public Token(String op) {
type = OPERATOR ;
this.op = op ;
}
public Token(double num) {
type = OPERAND ;
this.num = num ;
}
public Token() {
type = PAREN ;
}
public int getType() {
return type ;
}
public double getNum() {
if(type != OPERAND)
throw new RuntimeException("Invalid call to Token::getNum") ;
return num ;
}
public String getOp() {
if(type != OPERATOR)
throw new RuntimeException("Invalid call to Token::getOp") ;
return op ;
}
public final static int OPERATOR = 1 ;
public final static int OPERAND = 2 ;
public final static int PAREN = 3 ;
private int type ;
private double num ;
private String op ;
}
