postfix.java

Convert infix to postfix

//Postfix.java
//Group 5

import java.util.EmptyStackException;

/**
 * A postfix calculator.
 * All operands must be positive integers.
 */
public class Postfix {

  public static void main(String[] args) {
    Postfix p = new Postfix();

	String a = "1+2.5*4 -5 /2.0 +3";
//	String a = "1+ (2.5*4-5) /2.0+3";
//	String a = "1+2.5*4-5/(2.0+3)";
    System.out.println("Infix: " + a);
	System.out.println("Postfix: " + p.InfixToPostfix(a));
    System.out.println("d1= " + p.getValue(p.InfixToPostfix(a)));
	double d2 = 1+2.5*4 -5 /2.0 +3;
//	double d2 = 1+ (2.5*4-5) /2.0+3;
//	double d2 = 1+2.5*4-5/(2.0+3);
	System.out.println("d2=" + d2);

  }

  /**
   * Converts the given infix expression into a postfix expression.
   */
  public String InfixToPostfix(String infixExpr) {
    StringBuffer infix = new StringBuffer(infixExpr);
    StringBuffer postfix = new StringBuffer();
    MyStack stack = new MyStack();
    
    try{
      while (infix.length() > 0) { //until all has been processed
        //operand -- move to postfix 
        if (Character.isDigit(infix.charAt(0))){
          if (postfix.length() > 0 && 
              Character.isDigit(postfix.charAt(postfix.length() - 1))) {
            //last postfix char is a digit, so append a space first
            postfix.append(' ');
          }
          //in the case of a single/first digit, just append
          postfix.append(infix.charAt(0)); //charAt(0) deleted below
          
          while (infix.length() > 1 && Character.isDigit(infix.charAt(1))){
            //there are additional digits to this number, so append all
            postfix.append(infix.charAt(1));
            infix.deleteCharAt(1);
          }
          
        //operators -- remove any operators of >= precedence, then push
        }else if (infix.charAt(0) == '+' || infix.charAt(0) == '-') {
          //pop any other operators
          while (!stack.empty() && 
                 this.isOperator( ((Character) stack.peek()).charValue() )) {
			  postfix.append(' ');
             postfix.append(stack.pop());
          }
		  postfix.append(' ');
          stack.push(new Character(infix.charAt(0)));         
        }else if (infix.charAt(0) == '*' || infix.charAt(0) == '/') {
          //pop only other '*' or '/'
          while (!stack.empty() && 
                 (((Character) stack.peek()).charValue() == '*' ||
                  ((Character) stack.peek()).charValue() == '/') ){ 
			  postfix.append(' ');
             postfix.append(stack.pop());
          }
		  postfix.append(' ');
          stack.push(new Character(infix.charAt(0)));                         

        // '(' -- stack it
        }else if (infix.charAt(0) == '('){
          stack.push(new Character(infix.charAt(0)));
        // ')' -- unstack until hit corresponding '(' 
        }else if (infix.charAt(0) == ')'){
          char popped = ((Character) stack.pop()).charValue();
          while (popped != '(') {
			  postfix.append(' ');
            postfix.append(popped);
            popped = ((Character) stack.pop()).charValue();
          }           
        
        //spaces
        }else if (infix.charAt(0) == ' ') {
          // just ignore and move on
        
		}else if (infix.charAt(0) == '.') {
			postfix.append(infix.charAt(0));
		
        //hit something we don't know how to process
        }else {
          throw new IllegalArgumentException();
        }

        //now remove the char just processed
        infix.deleteCharAt(0);
      }
      //done with infix, but not with stack
      while (!stack.empty()) {
		  postfix.append(' ');
        postfix.append(stack.pop());
      }
    
    }catch (EmptyStackException ese) {
      //popped something when we shouldn't have, so bad input
      throw new IllegalArgumentException();
    }

    return postfix.toString();
  }

  /**
   * Evalutes a given postfix expression and returns the results.
   */
  public float getValue(String postfixExpr) {
    MyStack stack = new MyStack();
    StringBuffer postfix = new StringBuffer(postfixExpr);
    try {
      while (postfix.length() > 0){
        if (Character.isDigit(postfix.charAt(0))) {  //operands
          //get all digits of this number
          StringBuffer num = new StringBuffer();
          while (postfix.length() > 0 && 
                 (Character.isDigit(postfix.charAt(0))||((postfix.charAt(0)) == '.'))) {
            num.append(postfix.charAt(0));
            postfix.deleteCharAt(0);
          }
          stack.push(new Float(num.toString()));
        }else { //operators
          Float rhs, lhs;
          switch (postfix.charAt(0)){

            case '+':
              rhs = new Float(stack.pop().toString());
              lhs = new Float(stack.pop().toString());
              stack.push(new Float(lhs.floatValue() + rhs.floatValue()));
              break;
            case '-':
              rhs = new Float(stack.pop().toString());
              lhs = new Float(stack.pop().toString());
              stack.push(new Float(lhs.floatValue() - rhs.floatValue()));
              break;
            case '*':
              rhs = new Float(stack.pop().toString());
              lhs = new Float(stack.pop().toString());
              stack.push(new Float(lhs.floatValue() * rhs.floatValue()));
              break;
            case '/':
              rhs = new Float(stack.pop().toString());
              lhs = new Float(stack.pop().toString());
              stack.push(new Float(lhs.floatValue() / rhs.floatValue()));
              break;
            case ' ':
              //do nothing with it
              break;
            default:
              //um... not supported
              throw new IllegalArgumentException();
          }
          postfix.deleteCharAt(0);
        }

      }
      //now postfix fully parsed
      float result = ((Float) stack.pop()).floatValue();
      if (!stack.empty()) { //then result not really the correct result
        throw new IllegalArgumentException();
      }else {
        return result;
      }  
    }catch (java.util.EmptyStackException ese){
      throw new IllegalArgumentException();
    }        
  }
    
  /**
   * Returns true if c is a operator
   */
  protected boolean isOperator(char c){
    switch (c){
      case '+':
      case '-':
      case '*':
      case '/':
        return true;
      default:
        return false;
    }
  }
  
}//end class


//DLLNode.class

/**
 * A doubly-linked Node.
 */
class DLLNode {

  private Object contents;
  private DLLNode next;
  private DLLNode prev;
  
  /**
   * Creates a new Node with no links
   */
  public DLLNode(Object contents) {
    this(contents, null, null);
  }
  
  /**
   * Create a new node with the given contents, and links
   */
  public DLLNode(Object contents, DLLNode prev, DLLNode next){
    this.setValue(contents);
    this.setNext(next);
    this.setPrev(prev);
  }


  /**
   * Sets this node to contain the given value
   */
  public void setValue(Object value) {
    this.contents = value;
  }
  
  /**
   * Returns this node's contents.
   */
  public Object getVal() {
    return this.contents;
  }
  
  /**
   * Set this node's next reference to the given node.
   */
  public void setNext(DLLNode next){
    this.next = next;
  }

  /**
   * Returns the next node in a list after this node.
   */ 
  public DLLNode getNext(){
    return this.next;
  }

  /**
   * Set this node's previous reference to the given node.
   */
  public void setPrev(DLLNode prev){
    this.prev = prev;
  }

  /**
   * Returns the node before this node in a list.
   */ 
  public DLLNode getPrev(){
    return this.prev;
  }

}


//Stack.class
// Stack Interface
interface Stack  {

public boolean empty();
 // Return whether the stack is empty.

public void push(Object x);
 // Push x onto the stack.

public Object peek();
 // Return the object at the top of the stack.

public Object pop();
 // Remove and return the object at the top of the  stack.
 
public void popAll();
 // Remove all items from the  stack.

} // end Stack  interface


//MyStack.class

/**
 * An linked-list implementation of a Stack.
 */
class MyStack implements Stack {
  /* 
   * IMPL NOTE: uses DLLNodes, even though singly-linked nodes are all 
   * that are actually required. 
   * Doesn't currently bother to set the prev links.
   */
  protected DLLNode top;
  
  /** Returns whether this stack is empty */
  public boolean empty(){
    return (top == null);
  }
  
  /** Pushes the given Object onto the top of this stack. */
  public void push(Object x){
    top = new DLLNode(x, null, top);
  }

  /** 
   * Returns the Object at the top of this stack.
   * The returned object is not removed or otherwise affected. 
   */
  public Object peek() {
    if (top == null) {
      throw new EmptyStackException();
    }else {
      return top.getVal();
    }
  }
  
  /** Removes and returns the Object at the top of the stack. */  
  public Object pop() {
    if (top == null) {
      throw new EmptyStackException();
    }else {
      DLLNode removed = top;
      top = top.getNext();
      return removed.getVal();
    }
  }
  
  /** Removes all objects from this stack, leaving this stack empty. */
  public void popAll(){
    top = null;
  }
  
  /* overrides Object.toString */
  public String toString() {
    String s = "[(top)>";
    DLLNode curr = top;
    while (curr != null) {
      s += " " + curr.getVal().toString();
      curr = curr.getNext();
    }
    s += "]";
    return s;
  }
}