//DLLNode.java /** * A doubly-linked Node. * Contains an Object, and references to the next and previous nodes. * * @author Zach Tomaszewski * @version 1 Oct 2004 */ public 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 * * @param value The new contents of this node. */ public void setValue(Object value) { this.contents = value; } /** * Returns this node's contents. */ public Object getValue() { return this.contents; } /** * Set this node's next reference to the given node. * * @param next The node this node should point to as next in a list. */ 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. * * @param prev The node this node should point to as coming before * it in a list. */ public void setPrev(DLLNode prev){ this.prev = prev; } /** * Returns the node before this node in a list. */ public DLLNode getPrev(){ return this.prev; } } //Stack.java // Java Example: Stack Interface // ICS211 - Nickles // This defines an interface for a class // that supports stack operations. // public 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.java import java.util.EmptyStackException; /** * An linked-list implementation of a Stack. * * @author Zach Tomaszewski * @version 15 Oct 2004 */ public 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.getValue(); } } /** 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.getValue(); } } /** 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.getValue().toString(); curr = curr.getNext(); } s += "]"; return s; } } //PostfixCalculator.java import java.util.EmptyStackException; /** * A postfix calculator. * Handles only the 4 basic arithmetic operators: "+", "-", "*", and "/". * When given infix expressions, will also handle "(" and ")". * All operands must be positive integers. * * @author Zach Tomaszewski * @version 16 Oct 2004 */ public class PostfixCalculator { /** * A few test cases. */ public static void main(String[] args) { PostfixCalculator calc = new PostfixCalculator(); String a = "3+ 4*9 -2/3"; System.out.println(a + " > " + calc.convertInfixToPostfix(a)); a = "(3+4) * (9 - 3) / 8"; System.out.println(a + " > " + calc.convertInfixToPostfix(a)); a = "(3+45) * (98 - 3) / 8"; System.out.println(a + " > " + calc.convertInfixToPostfix(a)); a = "8 4 + 24 6 / /"; System.out.println(a + " > " + calc.evaluate(a)); } /* * XXX: The following code is a little hairy. Perhaps it would have * been clearer to go the recursive route... */ /** * Converts the given infix expression into a postfix expression. * Uses a minimal number of spaces in the resulting postfix--only used * between consecutive numbers. * * BUG/ODDITY: Will parse some incorrect infix expressions into equivalent * incorrect postfix expressions. * * @param infix A properly formatted infix expression. * @return the equivalent postfix expression * @throws IllegalArgumentException if the passed infix expression is not * a valid or complete expression or includes unsupported * chars */ public String convertInfixToPostfix(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(stack.pop()); } 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(stack.pop()); } 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(popped); popped = ((Character) stack.pop()).charValue(); } //spaces }else if (infix.charAt(0) == ' ') { // just ignore and move on //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(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. * * @param postfixExpr a valid postfix expression * @return the result of evaluting postfixExpr * @throws IllegalArgumentException if the given postfixExpr is found * to be invalid */ public float evaluate(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))) { 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 legitimate operator for this calculator */ protected boolean isOperator(char c){ switch (c){ case '+': case '-': case '*': case '/': return true; default: return false; } } }//end class //QuitButton.java import java.awt.*; import java.awt.event.*; /** * A Button that will, when clicked, close whatever window it is placed in. * * @author Zach Tomaszewski * @version 21 Oct 2004 */ public class QuitButton extends Button implements ActionListener { protected Window parent; /** * Creates a new QuitButton * * @param parent The window this button will close when pressed. */ public QuitButton(Window parent){ super("Quit"); this.parent = parent; this.addActionListener(this); } /** * Closes and exits the program/thread that is this button's parent. */ public void actionPerformed (ActionEvent e) { this.setEnabled(false); parent.dispose(); System.exit(0); } } //CalculatButton.java import java.awt.*; import java.awt.event.*; /** * A Button that, when clicked, will convert an infix expression into * a postfix expression and display the result. * * @author Zach Tomaszewski * @version 25 Oct 2004 */ public class CalculateButton extends Button implements ActionListener { protected TextField infix; protected TextField result; protected PostfixCalculator calc; /** * Creates a new CalculateButton * * @param infix The field to get the infix expression from; * will replace the expression with a postfix version * @param result The field in which to display the computed results, * or any errors that might occur. */ public CalculateButton(TextField infix, TextField result){ super("Calculate"); this.infix = infix; this.result = result; this.calc = new PostfixCalculator(); this.addActionListener(this); } /** * Reads the text from this button's registered infix textfield * and evalutes it as an infix expression, displaying the result * in this button's registered result textfield. Also converts the * infix expression to its corresponding postfix form. Will display * any error messages in the result textfield. */ public void actionPerformed (ActionEvent e) { this.setEnabled(false); try { //do coversion and calculation first String postfix = calc.convertInfixToPostfix(infix.getText()); float value = calc.evaluate(postfix); //if haven't thrown an exception yet, then good input infix.setText(postfix); result.setText(new Float(value).toString()); }catch (IllegalArgumentException iae) { //coversion or calculation failed, so bad input result.setText("Could not parse your (invalid) infix expression."); } this.setEnabled(true); } } //PostfixCalcFrame.java import java.awt.*; import java.awt.event.*; /** * A GUI window for a postfix calculator. * * @author Zach Tomaszewski * @version 19 Oct 2004 */ class PostfixCalcFrame extends Frame { //interface components private TextField input, output; private Button eval, quit; /** * Constructs a new frame containing the GUI. * This includes a input textfield, and output textfield, a Calculate * button and a Quit button. */ public PostfixCalcFrame() { /* based on David Nickles's TalkBox */ // Set up the window. this.setTitle("Postfix Calculator"); // window title this.setBackground(Color.white); // background color this.setSize(300,200); // window size: (width,height) pixels //create components input = new TextField("", 20); output = new TextField("", 20); output.setEditable(false); eval = new CalculateButton(input, output); quit = new QuitButton(this); //add components this.setLayout(new FlowLayout()); // window layout manager this.add(new Label("Infix Expression:")); this.add(input); this.add(eval); this.add(quit); this.add(new Label("Result:")); this.add(output); //get the close/X window button to work, using an anonymous inner class this.addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent we) { we.getWindow().dispose(); } }); show(); // Show (popup) the window. } /** * Run PostfixCalcFrame as a stand-alone application. */ public static void main(String[] args) { PostfixCalcFrame pfc = new PostfixCalcFrame (); pfc.setVisible(true); } }//end class //PostfixCalcApplet.java import java.awt.*; import java.awt.event.*; import java.applet.*; /** * An applet that provides instructions and interface * for a postfix calculator. * * @author Zach Tomaszewski * @version 21 Oct 2004 */ public class PostfixCalcApplet extends Applet implements ActionListener{ public String usage; protected Frame calc; protected Button start; public PostfixCalcApplet() { usage = "Enter an infix expression and click the 'Evaluate' button.\n"; usage += "Your expression will be converted into an equivalent postfix\n"; usage += "expression, and the result will be given.\n\n"; usage += "This calculator supports the four basic arithmetic operators,\n"; usage += "parentheses, spaces, and positive integers of more than one\n"; usage += "digit."; } public void init() { this.setLayout(new BorderLayout()); this.add(new TextArea(this.usage), BorderLayout.NORTH); start = new Button("Start Calculator"); start.addActionListener(this); this.add(start, BorderLayout.SOUTH); } /** * Will start a new PostfixCalcFrame instance. * Disposes any running instance first. */ public void actionPerformed(ActionEvent ae) { if (calc != null) { calc.dispose(); calc = null; } calc = new PostfixCalcFrame(); calc.setVisible(true); } /** * Will display usage message and start a calc instance. */ public static void main(String[] args) { PostfixCalcApplet calc = new PostfixCalcApplet(); System.out.println(calc.usage); calc.actionPerformed(new ActionEvent(calc, ActionEvent.ACTION_PERFORMED, "start")); } }//end class