Code Pretty Print Script

Saturday, November 16, 2013

Stack (Unbound)

Implementing an abstract data type like an unbounded Stack allows its' use with a two stack arbitrary precision machine. This Stack provides peek(), pop() and push().
Inspired by Dan's question on Stack Overflow.
Given this "program", the Stack will have one number at the top (i.e. 12).
( 3 * 4 ) .

/*
 * Copyright © 2013 - Elliott Frisch
 * 
 * THIS SOFTWARE IS PROVIDED UNDER THE CREATIVE COMMONS
 * LICENSE 3.0 "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR
 * A PARTICULAR PURPOSE.
 * 
 * To use this software you must agree to the complete
 * license terms available at:
 * http://creativecommons.org/licenses/by/3.0/us/deed.en_US
 * 
 * It is the intent of the author(s) that you may use or
 * modify this software for any purpose (including your own
 * commercial gain) provided that this notice remains in its
 * entirety.
 * 
 * Created by Elliott Frisch - www.frischcode.com 
 * Daniel Brackett           - www.danielbrackett.com
 */
package com.frischcode.util;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * <b>Rationale:</b> Implementing a basic Stack. Then
 * demonstrate an arbitrary precision math REPL with two
 * unbounded Stacks. Inspired by <a
 * href="http://stackoverflow.com/users/1516132/dan"
 * >Dan</a>'s question on <a href=
 * "http://stackoverflow.com/questions/19988147/stack-adding-machine-0doesnt-add-but-hangs-waiting-for-more-args"
 * >Stack Overflow</a>.
 * 
 * @author Elliott Frisch
 * 
 * @param <T>
 *          A generic stack container.
 */
public class Stack<T> {
  private static final String UNDERFLOW = "Stack underflow error. Continuing.";
  private static final String OVERFLOW = "Stack over-flow error. Continuing.";

  private static final void say(String in) {
    if (in != null) {
      if (in.length() > 0) {
        System.out.println(in);
        System.out.flush();
      }
    }
  }

  private static final void underFlow() {
    say(UNDERFLOW);
  }

  private static final void overFlow() {
    say(OVERFLOW);
  }

  private enum Operators {
    ADD("+"), SUB("-"), MULTIPLY("*"), DIVIDE("/"), POW(
        "^");
    Operators(String oper) {
      _oper = oper;
    }

    private String _oper;

    public String toString() {
      return _oper;
    }

    public BigDecimal execute(BigDecimal a,
        BigDecimal b) {
      switch (this) {
      case ADD:
        return a.add(b);
      case SUB:
        return b.subtract(a);
      case MULTIPLY:
        return a.multiply(b);
      case DIVIDE:
        return b.divide(a);
      case POW:
        return a.pow(b.intValue());
      }
      return null;
    }

    public static Operators matchOper(String in) {
      if (in != null) {
        in = in.trim();
        for (Operators oper : Operators.values()) {
          if (oper.toString().equals(in)) {
            return oper;
          }
        }
      }
      return null;
    }
  }

  private List<T> a;

  public static void main(String[] args) {
    Stack<String> ops = new Stack<String>(5);
    Stack<BigDecimal> vals = new Stack<BigDecimal>(100);
    say("REPL loaded - BEGIN");
    Scanner console = new Scanner(System.in);
    try {
      while (console.hasNext()) {
        String str = console.next().trim();
        if (str.equals(".")) {
          say(vals.peek().toString());
        } else if (str.equals("(")) {
          ;
        } else if (Operators.matchOper(str) != null) {
          ops.push(str);
        } else if (str.equals(")") || str.equals("=")) {
          Operators op = Operators
              .matchOper(ops.pop());
          if (op != null) {
            BigDecimal a = vals.pop();
            BigDecimal b = vals.pop();
            if (a != null && b != null) {
              a = op.execute(a, b);
            }
            if (a != null) {
              vals.push(a);
            }
          }
        } else {
          try {
            final BigDecimal a = new BigDecimal(str);
            if (a != null) {
              vals.push(a);
            }
          } catch (Exception e) {
            say(e.getMessage() + ": " + str);
          }
        }
      }
    } finally {
      console.close();
    }
  }

  /**
   * Construct an Empty Stack. Default to an initial
   * capacity of 10.
   */
  public Stack() {
    this(10);
  }

  /**
   * Construct a Stack with an initial capacity of cap.
   * 
   * @param cap
   *          An initial capacity size.
   */
  public Stack(int cap) {
    a = new ArrayList<T>(cap);
  }

  /**
   * Pushes an Item onto this Stack. Ignores null.
   * 
   * @param item
   *          The item to push onto the stack.
   */
  public void push(T item) {
    if (item != null && !isFull()) {
      a.add(item);
    } else {
      overFlow();
    }
  }

  /**
   * Pops the top item off the stack. Null if empty.
   * 
   * @return The top item on the stack. Removes it.
   */
  public T pop() {
    if (!isEmpty()) {
      return a.remove(a.size() - 1);
    }
    underFlow();
    return null;
  }

  /**
   * Returns the item at the top of the Stack. That is what
   * pop() would return without modifying the Stack.
   * 
   * @return The top item on the stack. Without removing it.
   */
  public T peek() {
    if (!isEmpty()) {
      return a.get(a.size() - 1);
    }
    underFlow();
    return null;
  }

  /**
   * This Stack is unbounded.
   * 
   * @return return false.
   */
  public boolean isFull() {
    return false;
  }

  /**
   * Return true if the Stack doesn't have any items.
   * 
   * @return true if the Stack contains no items.
   */
  public boolean isEmpty() {
    return a.size() == 0;
  }

  /**
   * The size of the stack + 1.
   * 
   * @return The size of the Stack + 1.
   */
  public int size() {
    return a.size();
  }
}

No comments :

Post a Comment