CSC212: Computer Science.
TEXTBOOK: Object-Oriented Data Structures Using Java
TEXTBOOK: Source Code
|
|
//----------------------------------------------------------------------
// Balanced.java by Dale/Joyce/Weems Chapter 3
//
// Checks for balanced expressions using standard rules.
//
// Matching pairs of open and close symbols are provided to the
// constructor through two string parameters.
//----------------------------------------------------------------------
import ch03.stacks.*;
public class Balanced
{
private String openSet;
private String closeSet;
public Balanced(String openSet, String closeSet)
// Preconditions: No character is contained more than once in the
// combined openSet and closeSet strings.
// The size of openSet = the size of closeSet.
{
this.openSet = openSet;
this.closeSet = closeSet;
}
public int test(String expression)
// Returns 0 if expression is balanced.
// Returns 1 if expression has unbalanced symbols.
// Returns 2 if expression came to end prematurely.
{
char currChar; // current expression character being studied
int currCharIndex; // index of current character
int lastCharIndex; // index of last character in the expression
int openIndex; // index of current character in openSet
int closeIndex; // index of current character in closeSet
boolean stillBalanced = true; // true as long as expression is balanced
BoundedStackInterface stack; // holds unmatched open symbols
stack = new ArrayStack(expression.length());
currCharIndex = 0;
lastCharIndex = expression.length() - 1;
while (stillBalanced && (currCharIndex <= lastCharIndex))
// while expression still balanced and not at end of expression
{
currChar = expression.charAt(currCharIndex);
openIndex = openSet.indexOf(currChar);
if(openIndex != -1) // if the current character is in the openSet
{
// Push the index onto the stack.
stack.push(openIndex);
}
else
{
closeIndex = closeSet.indexOf(currChar);
if(closeIndex != -1) // if the current character is in the closeSet
{
try // try to pop an index off the stack
{
openIndex = stack.top();
stack.pop();
if (openIndex != closeIndex) // if popped index doesn't match
{
stillBalanced = false; // then expression is not balanced
}
}
catch(StackUnderflowException e) // if stack was empty
{
stillBalanced = false; // then expression is not balanced
}
}
}
currCharIndex++; // set up processing of next character
}
if (!stillBalanced)
return 1; // unbalanced symbols
else
if (!stack.isEmpty())
return 2; // premature end of expression
else
return 0; // expression is balanced
}
}
|
|
|
//----------------------------------------------------------------------
// BalancedApp.java by Dale/Joyce/Weems Chapter 3
//
// Checks for balanced grouping symbols.
// Input consists of a sequence of expressions, one per line.
// Special symbol types are (), [], and {}.
//----------------------------------------------------------------------
import java.util.Scanner;
public class BalancedApp
{
public static void main(String[] args)
{
Scanner conIn = new Scanner(System.in);
// Instantiate new Balanced class with grouping symbols.
Balanced bal = new Balanced("([{", ")]}");
int result; // 0 = balanced, 1 = unbalanced,
// 2 = premature end
String expression = null; // expression to be evaluated
String more = null; // used to stop or continue processing
do
{
// Get next expression to be processed.
System.out.println("Enter an expression to be evaluated: ");
expression = conIn.nextLine();
// Obtain and output result of balanced testing.
result = bal.test(expression);
if (result == 1)
System.out.println("Unbalanced symbols ");
else
if (result == 2)
System.out.println("Premature end of expression");
else
System.out.println("The symbols are balanced.");
// Determine if there is another expression to process.
System.out.println();
System.out.print("Evaluate another expression? (Y=Yes): ");
more = conIn.nextLine();
System.out.println();
}
while (more.equalsIgnoreCase("y"));
}
}
|
|
|
//----------------------------------------------------------------------
// PFixConsole.java by Dale/Joyce/Weems Chapter 3
//
// Evaluates posfix expressions entered by the user.
// Uses a Console interface.
//----------------------------------------------------------------------
import java.util.Scanner;
import ch03.postfix.*;
public class PFixConsole
{
public static void main(String[] args)
{
Scanner conIn = new Scanner(System.in);
String line = null; // string to be evaluated
String more = null; // used to stop or continue processing
int result; // result of evaluation
do
{
// Get next expression to be processed.
System.out.println("Enter a postfix expression to be evaluated: ");
line = conIn.nextLine();
// Obtain and output result of expression evaluation.
try
{
result = PostFixEvaluator.evaluate(line);
// Output result.
System.out.println();
System.out.println("Result = " + result);
}
catch (PostFixException error)
{
// Output error message.
System.out.println();
System.out.println("Error in expression - " + error.getMessage());
}
// Determine if there is another expression to process.
System.out.println();
System.out.print("Evaluate another expression? (Y=Yes): ");
more = conIn.nextLine();
System.out.println();
}
while (more.equalsIgnoreCase("y"));
System.out.println("Program completed.");
}
}
|
|
|
//----------------------------------------------------------------------
// PFixGUI.java by Dale/Joyce/Weems Chapter 3
//
// Evaluates posfix expressions entered by the user.
// Uses a graphical user interface.
//----------------------------------------------------------------------
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.border.*;
import java.io.*;
import ch03.postfix.*;
public class PFixGUI
{
// text field
private static JTextField expressionText; // text field for postfix expression
// status Label
private static JLabel statusLabel; // label for status/result info
// Define a button listener.
private static class ActionHandler implements ActionListener
{
public void actionPerformed(ActionEvent event)
// listener for the button events
{
if (event.getActionCommand().equals("Evaluate"))
{ // Handles Evaluate event.
int result = 0;
String errMessage = null;
try
{
result = PostFixEvaluator.evaluate(expressionText.getText());
statusLabel.setText("Result = " + result);
}
catch (PostFixException error)
{
errMessage = error.getMessage();
statusLabel.setText("Result = " + errMessage);
}
}
else
if (event.getActionCommand().equals("Clear"))
{ // Handles Clear event.
statusLabel.setText("cleared");
expressionText.setText("");
}
}
}
public static void main(String args[]) throws IOException
{
// Declare/instantiate/initialize display frame.
JFrame displayFrame = new JFrame();
displayFrame.setTitle("PostFix Expression Evaluator Program");
displayFrame.setSize(400,100);
displayFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
// displayFrame.setDefaultCloseOperation(3);
// text box for expression
expressionText = new JTextField("postfix expression goes here", 60);
// Status/Result label
statusLabel = new JLabel("status", JLabel.CENTER);
statusLabel.setBorder(new LineBorder(Color.red,3));
// Evaluate and clear buttons
JButton evaluate = new JButton("Evaluate");
JButton clear = new JButton("Clear");
// Button event listener
ActionHandler action = new ActionHandler();
// Register button listeners.
evaluate.addActionListener(action);
clear.addActionListener(action);
// Instantiate content pane and information panels.
Container contentPane = displayFrame.getContentPane();
JPanel expressionPanel = new JPanel();
JPanel buttonPanel = new JPanel();
// Initialize expression panel.
expressionPanel.setLayout(new GridLayout(2,1));
expressionPanel.add(expressionText);
expressionPanel.add(statusLabel);
// Initialize button panel.
buttonPanel.setLayout(new GridLayout(1,2));
buttonPanel.add(evaluate);
buttonPanel.add(clear);
// Set up and show the frame.
contentPane.add(expressionPanel, "North");
contentPane.add(buttonPanel, "Center");
displayFrame.pack();
displayFrame.setVisible(true);
}
}
|
|
|
//----------------------------------------------------------------------
// PostFixEvaluator.java by Dale/Joyce/Weems Chapter 3
//
// Provides a postfix expression evaluation.
//----------------------------------------------------------------------
package ch03.postfix;
import ch03.stacks.*;
import java.util.Scanner;
public class PostFixEvaluator
{
public static int evaluate(String expression)
{
BoundedStackInterface stack = new ArrayStack(50);
int value;
String operator;
int operand1;
int operand2;
int result = 0;
Scanner tokenizer = new Scanner(expression);
while (tokenizer.hasNext())
{
if (tokenizer.hasNextInt())
{
// Process operand.
value = tokenizer.nextInt();
if (stack.isFull())
throw new PostFixException("Too many operands - stack overflow");
stack.push(value);
}
else
{
// Process operator.
operator = tokenizer.next();
// Obtain second operand from stack.
if (stack.isEmpty())
throw new PostFixException("Not enough operands - stack underflow");
operand2 = stack.top();
stack.pop();
// Obtain first operand from stack.
if (stack.isEmpty())
throw new PostFixException("Not enough operands - stack underflow");
operand1 = stack.top();
stack.pop();
// Perform operation.
if (operator.equals("/"))
result = operand1 / operand2;
else
if(operator.equals("*"))
result = operand1 * operand2;
else
if(operator.equals("+"))
result = operand1 + operand2;
else
if(operator.equals("-"))
result = operand1 - operand2;
else
throw new PostFixException("Illegal symbol: " + operator);
// Push result of operation onto stack.
stack.push(result);
}
}
// Obtain final result from stack.
if (stack.isEmpty())
throw new PostFixException("Not enough operands - stack underflow");
result = stack.top();
stack.pop();
// Stack should now be empty.
if (!stack.isEmpty())
throw new PostFixException("Too many operands - operands left over");
// Return the final.
return result;
}
}
|
|
|
package ch03.postfix;
public class PostFixException extends RuntimeException
{
public PostFixException()
{
super();
}
public PostFixException(String message)
{
super(message);
}
}
|
|
|
//----------------------------------------------------------------------
// ReverseStrings.java by Dale/Joyce/Weems Chapter 3
//
// Sample use of stack. Outputs strings in reverse order of entry.
//----------------------------------------------------------------------
import ch03.stacks.*;
import java.util.Scanner;
public class ReverseStrings
{
public static void main(String[] args)
{
Scanner conIn = new Scanner(System.in);
BoundedStackInterface stack;
stack = new ArrayStack(3);
String line;
for (int i = 1; i <= 3; i++)
{
System.out.print("Enter a line of text > ");
line = conIn.nextLine();
stack.push(line);
}
System.out.println("\nReverse is:\n");
while (!stack.isEmpty())
{
line = stack.top();
stack.pop();
System.out.println(line);
}
}
}
|
|
|
//----------------------------------------------------------------------
// ReverseStrings2.java by Dale/Joyce/Weems Chapter 3
//
// Sample use of the library Stack.
// Outputs strings in reverse order of entry.
//----------------------------------------------------------------------
import java.util.Stack;
import java.util.Scanner;
public class ReverseStrings2
{
public static void main(String[] args)
{
Scanner conIn = new Scanner(System.in);
Stack stack = new Stack();
String line;
for (int i = 1; i <= 3; i++)
{
System.out.print("Enter a line of text > ");
line = conIn.nextLine();
stack.push(line);
}
System.out.println("\nReverse is:\n");
while (!stack.empty())
{
line = stack.peek();
stack.pop();
System.out.println(line);
}
}
}
|
|
|
//----------------------------------------------------------------------
// ArrayListStack.java by Dale/Joyce/Weems Chapter 3
//
// Implements UnboundedStackInterface using an ArrayList to
// hold the stack elements.
//----------------------------------------------------------------------
package ch03.stacks;
import java.util.*;
public class ArrayListStack implements UnboundedStackInterface
{
protected ArrayList stack; // ArrayList that holds stack elements
public ArrayListStack()
{
stack = new ArrayList();
}
public void push(T element)
// Places element at the top of this stack.
{
stack.add(element);
}
public void pop()
// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
{
if (!isEmpty())
{
stack.remove(stack.size() - 1);
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public T top()
// Throws StackUnderflowException if this stack is empty,
// otherwise returns top element from this stack.
{
T topOfStack = null;
if (!isEmpty())
topOfStack = stack.get(stack.size() - 1);
else
throw new StackUnderflowException("Top attempted on an empty stack.");
return topOfStack;
}
public boolean isEmpty()
// Returns true if this stack is empty, otherwise returns false.
{
if (stack.size() == 0)
return true;
else
return false;
}
}
|
|
|
//----------------------------------------------------------------
// ArrayStack.java by Dale/Joyce/Weems Chapter 3
//
// Implements BoundedStackInterface using an array to hold the
// stack elements.
//
// Two constructors are provided: one that creates an array of a
// default size and one that allows the calling program to
// specify the size.
//----------------------------------------------------------------
package ch03.stacks;
public class ArrayStack implements BoundedStackInterface
{
protected final int DEFCAP = 100; // default capacity
protected T[] stack; // holds stack elements
protected int topIndex = -1; // index of top element in stack
public ArrayStack()
{
stack = (T[]) new Object[DEFCAP];
}
public ArrayStack(int maxSize)
{
stack = (T[]) new Object[maxSize];
}
public void push(T element)
// Throws StackOverflowException if this stack is full,
// otherwise places element at the top of this stack.
{
if (!isFull())
{
topIndex++;
stack[topIndex] = element;
}
else
throw new StackOverflowException("Push attempted on a full stack.");
}
public void pop()
// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
{
if (!isEmpty())
{
stack[topIndex] = null;
topIndex--;
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public T top()
// Throws StackUnderflowException if this stack is empty,
// otherwise returns top element from this stack.
{
T topOfStack = null;
if (!isEmpty())
topOfStack = stack[topIndex];
else
throw new StackUnderflowException("Top attempted on an empty stack.");
return topOfStack;
}
public boolean isEmpty()
// Returns true if this stack is empty, otherwise returns false.
{
if (topIndex == -1)
return true;
else
return false;
}
public boolean isFull()
// Returns true if this stack is full, otherwise returns false.
{
if (topIndex == (stack.length - 1))
return true;
else
return false;
}
}
|
|
|
//----------------------------------------------------------------------------
// BoundedStackInterface.java by Dale/Joyce/Weems Chapter 3
//
// Interface for a class that implements a stack of with a bound
// on the size of the stack. A stack is a last-in, first-out structure.
//----------------------------------------------------------------------------
package ch03.stacks;
public interface BoundedStackInterface extends StackInterface
{
void push(T element) throws StackOverflowException;
// Throws StackOverflowException if this stack is full,
// otherwise places element at the top of this stack.
boolean isFull();
// Returns true if this stack is full, otherwise returns false.
}
|
|
|
//----------------------------------------------------------------------
// LinkedStack.java by Dale/Joyce/Weems Chapter 3
//
// Implements UnboundedStackInterface using a linked list
// to hold the stack elements.
//-----------------------------------------------------------------------
package ch03.stacks;
import support.LLNode;
public class LinkedStack implements UnboundedStackInterface
{
protected LLNode top; // reference to the top of this stack
public LinkedStack()
{
top = null;
}
public void push(T element)
// Places element at the top of this stack.
{
LLNode newNode = new LLNode(element);
newNode.setLink(top);
top = newNode;
}
public void pop()
// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
{
if (!isEmpty())
{
top = top.getLink();
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public T top()
// Throws StackUnderflowException if this stack is empty,
// otherwise returns top element from this stack.
{
if (!isEmpty())
return top.getInfo();
else
throw new StackUnderflowException("Top attempted on an empty stack.");
}
public boolean isEmpty()
// Returns true if this stack is empty, otherwise returns false.
{
if (top == null)
return true;
else
return false;
}
}
|
|
|
//----------------------------------------------------------------------------
// StackInterface.java by Dale/Joyce/Weems Chapter 3
//
// Interface for a class that implements a stack of .
// A stack is a last-in, first-out structure.
//----------------------------------------------------------------------------
package ch03.stacks;
public interface StackInterface
{
void pop() throws StackUnderflowException;
// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
T top() throws StackUnderflowException;
// Throws StackUnderflowException if this stack is empty,
// otherwise returns top element from this stack.
boolean isEmpty();
// Returns true if this stack is empty, otherwise returns false.
}
|
|
|
package ch03.stacks;
public class StackOverflowException extends RuntimeException
{
public StackOverflowException()
{
super();
}
public StackOverflowException(String message)
{
super(message);
}
}
|
|
|
package ch03.stacks;
public class StackUnderflowException extends RuntimeException
{
public StackUnderflowException()
{
super();
}
public StackUnderflowException(String message)
{
super(message);
}
}
|
|
|
//----------------------------------------------------------------------------
// UnboundedStackInterface.java by Dale/Joyce/Weems Chapter 3
//
// Interface for a class that implements a stack of with no bound
// on the size of the stack. A stack is a last-in, first-out structure.
//----------------------------------------------------------------------------
package ch03.stacks;
public interface UnboundedStackInterface extends StackInterface
{
void push(T element);
// Places element at the top of this stack.
}
|