Instructions
Objective
Write a java assignment program to implement a node, linked stack, stack apps in programming language.
Requirements and Specifications
Implement a program showing all the stacks, linked stacks, stack apps, etc through various programs in java programming language.
Source Code
CHAR STACK
// The CharStack class that implements a stack of characters
// Xiwei Wang
public class CharStack
{
// instance variables
private char[] m_array;
private int m_index;
// constructor
public CharStack(int cap)
{
m_array = new char[cap];
m_index = 0;
}
// check whether the stack is empty
public boolean isEmpty()
{
if (m_index == 0)
return true;
else
return false;
}
// return the element at the top of the stack
public char top()
{
if (isEmpty())
throw new RuntimeException("top attempted on an empty stack");
else
return m_array[m_index - 1];
}
// push a character onto the stack
public void push(char c)
{
m_array[m_index] = c;
m_index++;
}
// remove and return the element at the top of the stack
public char pop()
{
if (isEmpty())
throw new RuntimeException("pop attempted on an empty stack");
else
{
char c = m_array[m_index - 1];
m_index--;
return c;
}
}
// return the number of elements on the stack
public int size()
{
return m_index;
}
// return a string representation of the stack
@Override
public String toString()
{
String stackContent = "";
for (int i = m_index - 1; i >= 0; i--)
stackContent += m_array[i];
return stackContent;
}
}
LINKED NUMBER STACK
// The linked list based implementation for the NumberStack ADT
// Your name here
public class LinkedNumberStack implements NumberStack {
// instance variable
private LNode m_top;
// check whether the stack is empty
public boolean isEmpty() {
if (m_top == null)
return true;
else
return false;
}
// check whether the stack is full
public boolean isFull() {
return false;
}
// return the element at the top of the stack
public int top() {
if (isEmpty())
throw new RuntimeException("top attempted on an empty stack");
else
return m_top.getInfo();
}
// push a value onto the stack
public void push(int v) {
LNode temp = new LNode(v);
temp.m_link = m_top;
m_top = temp;
}
// remove and return the value at the top of the stack
public int pop() {
if (isEmpty())
throw new RuntimeException("pop attempted on an empty stack");
int data = m_top.getInfo();
m_top = m_top.getLink();
return data;
}
// return the number of elements on the stack
public int size() {
int size = 0;
LNode temp = m_top;
while (temp != null) {
size++;
temp = temp.m_link;
}
return size;
}
// return a string representation of the stack
@Override
public String toString() {
String stackContent = "";
LNode current = m_top;
while (current != null) {
stackContent += current.getInfo() + " ";
current = current.getLink();
}
return stackContent;
}
}
L NODE
// The LNode class that represents a node in linked lists
// Do not make any changes to this file!
// Xiwei Wang
public class LNode
{
// instance variables
int m_info;
LNode m_link;
// constructor
public LNode(int info)
{
m_info = info;
m_link = null;
}
// member methods
public void setLink(LNode link)
{
m_link = link;
}
public LNode getLink()
{
return m_link;
}
public int getInfo()
{
return m_info;
}
}
NUMBER STACK
// The NumberStack interface
// Do not make any changes to this file!
// Xiwei Wang
public interface NumberStack
{
boolean isEmpty(); // check whether the stack is empty
boolean isFull(); // check whether the stack is full
int top(); // return the element at the top of the stack
int pop(); // remove and return the element at the top of the stack
void push(int v); // push a value onto the stack
int size(); // return the number of elements on the stack
@Override
String toString(); // return a string representation of the stack
}
STACK APPS
// The StackApps class that implements two Stack applications
// Your name here
public class StackApps
{
// evaluate the expression of signs saved in a stack in an xor fashion (see HW specs for details)
// Do not create any arrays or any other structures! Doing so will result in points deduction.
// You can use the auxiliary stack that is created for you in your implementation.
public char evaluateSigns(CharStack signs)
{
CharStack aux = new CharStack(64); // stack used to store the result binary number
while (signs.size() > 1) {
char top = signs.pop();
while (!signs.isEmpty()) {
char curr = signs.pop();
boolean val = (top == '+') ^ (curr == '+');
aux.push(val ? '+' : '-');
top = curr;
}
if (aux.size() == 1) {
signs.push(aux.pop());
}
else {
top = aux.pop();
while (!aux.isEmpty()) {
char curr = aux.pop();
boolean val = (top == '+') ^ (curr == '+');
signs.push(val ? '+' : '-');
top = curr;
}
}
}
return signs.top(); // return the top of the stack that saves the final result
}
// add num1 and num2 (both represented as CharStacks), and save the result on a stack
// Do not create any arrays! Do not use any Java libraries to do the calculation.
// Doing so will result in points deduction.
public String addBigInteger(CharStack num1, CharStack num2)
{
CharStack stackResult = new CharStack(64); // stack used to store the result of the sum
int carry = 0;
while (!num1.isEmpty() && !num2.isEmpty()) {
int n1 = num1.pop() - '0';
int n2 = num2.pop() - '0';
int sum = carry + n1 + n2;
carry = sum / 10;
stackResult.push((char)((sum) % 10 + '0'));
}
CharStack nonEmpty = num1.isEmpty() ? num2 : num1;
while (!nonEmpty.isEmpty()) {
int n1 = num1.pop() - '0';
int sum = carry + n1;
carry = sum / 10;
stackResult.push((char)((sum) % 10 + '0'));
}
if (carry != 0) {
stackResult.push((char)(carry + '0'));
}
return stackResult.toString(); // return a string representation of the stack
}
}
TEST STACK
// Test driver for the LinkedNumberStack and StackApps classes
// Do not make any changes to this file!
// Xiwei Wang
import java.util.*;
import java.io.*;
public class TestStack
{
public static void main(String[] args)
{
System.out.println("================ Problem 1 ================");
TestP1();
System.out.println("================ End of Problem 1 ================\n\n");
System.out.print("Press any key to test Problem 2...");
try
{
System.in.read();
}
catch (Exception e)
{
e.printStackTrace();
}
System.out.println("================ Problem 2 ================");
TestP2();
System.out.println("================ End of Problem 2 ================");
}
public static void TestP1()
{
NumberStack myStack = new LinkedNumberStack();
int numPassedTests = 0;
int numTotalTests = 0;
String testResult;
// Test 1
numTotalTests++;
int iReturn = -1;
testResult = "[Failed]";
String eMsg = "N/A";
try
{
iReturn = myStack.size();
if (iReturn == 0)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": size() ==> " + testResult + "\n Expected: 0" );
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 2
numTotalTests++;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.pop();
}
catch (RuntimeException e)
{
if (!(e instanceof NullPointerException))
{
numPassedTests++;
testResult = "[Passed]";
}
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": pop() ==> " + testResult + "\n Expected: a RuntimeException");
System.out.println(" Yours: " + eMsg + "\n");
// Test 3
numTotalTests++;
boolean bReturn = false;
testResult = "[Failed]";
eMsg = "N/A";
try
{
myStack.push(10);
bReturn = myStack.isEmpty();
if (bReturn == false)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": push(10) and then isEmpty() ==> " + testResult + "\n Expected: false");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + bReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 4
numTotalTests++;
String sReturn = myStack.toString();
if (sReturn.equals("10 "))
{
numPassedTests++;
testResult = "[Passed]";
}
else
testResult = "[Failed]";
System.out.println("Test " + numTotalTests + ": toString() ==> " + testResult + "\n Expected (from top to bottom): 10 ");
System.out.println(" Yours (from top to bottom): " + sReturn + "\n");
// Test 5
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.top();
if (iReturn == 10)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": top() ==> " + testResult + "\n Expected: 10");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 6
numTotalTests++;
sReturn = "";
testResult = "[Failed]";
eMsg = "N/A";
try
{
myStack.push(20);
sReturn = myStack.toString();
if (sReturn.equals("20 10 "))
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": push(20) and then toString() ==> " + testResult + "\n Expected (from top to bottom): 20 10 ");
if (eMsg.equals("N/A"))
System.out.println(" Yours (from top to bottom): " + sReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 7
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.top();
if (iReturn == 20)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": top() ==> " + testResult + "\n Expected: 20");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 8
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.pop();
if (iReturn == 20)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": pop() ==> " + testResult + "\n Expected: 20");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 9
numTotalTests++;
sReturn = myStack.toString();
if (sReturn.equals("10 "))
{
numPassedTests++;
testResult = "[Passed]";
}
else
testResult = "[Failed]";
System.out.println("Test " + numTotalTests + ": toString() ==> " + testResult + "\n Expected (from top to bottom): 10 ");
System.out.println(" Yours (from top to bottom): " + sReturn + "\n");
// Test 10
numTotalTests++;
sReturn = "";
testResult = "[Failed]";
eMsg = "N/A";
try
{
myStack.push(30);
myStack.push(40);
myStack.push(50);
sReturn = myStack.toString();
if (sReturn.equals("50 40 30 10 "))
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": push(30), push(40), push(50), and then toString() ==> " + testResult + "\n Expected (from top to bottom): 50 40 30 10 ");
if (eMsg.equals("N/A"))
System.out.println(" Yours (from top to bottom): " + sReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 11
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.size();
if (iReturn == 4)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": size() ==> " + testResult + "\n Expected: 4" );
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 12
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.pop();
iReturn = myStack.top();
if (iReturn == 40)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": pop() and then top() ==> " + testResult + "\n Expected: 40");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 13
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.pop();
iReturn = myStack.size();
if (iReturn == 2)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": pop() and then size() ==> " + testResult + "\n Expected: 2");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 14
numTotalTests++;
sReturn = "";
testResult = "[Failed]";
eMsg = "N/A";
try
{
myStack.push(20);
sReturn = myStack.toString();
if (sReturn.equals("20 30 10 "))
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": push(20) and then toString() ==> " + testResult + "\n Expected (from top to bottom): 20 30 10 ");
if (eMsg.equals("N/A"))
System.out.println(" Yours (from top to bottom): " + sReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 15
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.size();
if (iReturn == 3)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": size() ==> " + testResult + "\n Expected: 3" );
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 16
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.pop();
iReturn = myStack.pop();
iReturn = myStack.top();
if (iReturn == 10)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": pop() twice and then top() ==> " + testResult + "\n Expected: 10");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 17
numTotalTests++;
sReturn = "";
testResult = "[Failed]";
eMsg = "N/A";
try
{
sReturn = myStack.toString();
if (sReturn.equals("10 "))
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": toString() ==> " + testResult + "\n Expected (from top to bottom): 10 ");
if (eMsg.equals("N/A"))
System.out.println(" Yours (from top to bottom): " + sReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 18
numTotalTests++;
bReturn = false;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.pop();
bReturn = myStack.isEmpty();
if (bReturn == true && iReturn == 10)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": pop() and then isEmpty() ==> " + testResult + "\n Expected: 10, true");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + ", " + bReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 19
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.size();
if (iReturn == 0)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": size() ==> " + testResult + "\n Expected: 0" );
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 20
numTotalTests++;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.pop();
}
catch (RuntimeException e)
{
if (!(e instanceof NullPointerException))
{
numPassedTests++;
testResult = "[Passed]";
}
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": pop() ==> " + testResult + "\n Expected: a RuntimeException");
System.out.println(" Yours: " + eMsg + "\n");
// Test 21
numTotalTests++;
sReturn = "";
testResult = "[Failed]";
eMsg = "N/A";
try
{
myStack.push(70);
sReturn = myStack.toString();
if (sReturn.equals("70 "))
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": push(70) and then toString() ==> " + testResult + "\n Expected (from top to bottom): 70 ");
if (eMsg.equals("N/A"))
System.out.println(" Yours (from top to bottom): " + sReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 22
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.top();
if (iReturn == 70)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": top() ==> " + testResult + "\n Expected: 70");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
// Test 23
numTotalTests++;
iReturn = -1;
testResult = "[Failed]";
eMsg = "N/A";
try
{
iReturn = myStack.pop();
iReturn = myStack.size();
if (iReturn == 0)
{
numPassedTests++;
testResult = "[Passed]";
}
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.println("Test " + numTotalTests + ": pop() and then size() ==> " + testResult + "\n Expected: 0");
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + iReturn + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
System.out.println("Total test cases: " + numTotalTests + "\nCorrect: " + numPassedTests + "\nWrong: " + (numTotalTests - numPassedTests));
}
public static void TestP2()
{
try
{
ObjectInputStream in = new ObjectInputStream(new FileInputStream("testNumbers.dat"));
StackApps myApps = new StackApps();
ArrayList results = new ArrayList<>();
ArrayList numbers = new ArrayList();
results = (ArrayList)in.readObject();
numbers = (ArrayList)in.readObject();
char cr;
String sr;
String eMsg;
String currentLine;
int numPassedTests = 0;
int numTotalTests = 0;
for (int i = 0; i < 9; i++)
{
numTotalTests++;
currentLine = numbers.get(i);
CharStack signs = new CharStack(64); // stack used to store the signs
// push digits of number 1 onto stack
for (int j = 0; j < currentLine.length(); j++)
signs.push(currentLine.charAt(j));
String strStack = signs.toString();
cr = ' ';
eMsg = "N/A";
try
{
cr = myApps.evaluateSigns(signs);
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.print("Test " + numTotalTests + ": evaluateSigns(" + strStack + ") ==> ");
if (cr == results.get(i).charAt(0))
{
System.out.println("[Passed]");
numPassedTests++;
}
else
System.out.println("[Failed]");
System.out.println(" Expected: " + results.get(i));
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + cr + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
}
for (int i = 9; i < numbers.size(); i++)
{
numTotalTests++;
currentLine = numbers.get(i);
String[] operands = currentLine.split(" ");
CharStack num1 = new CharStack(64); // stack used to store number 1
CharStack num2 = new CharStack(64); // stack used to store number 2
// push digits of number 1 onto stack
for (int j = 0; j < operands[0].length(); j++)
num1.push(operands[0].charAt(j));
// push digits of number 2 onto stack
for (int j = 0; j < operands[1].length(); j++)
num2.push(operands[1].charAt(j));
sr = "";
eMsg = "N/A";
try
{
sr = myApps.addBigInteger(num1, num2);
}
catch (RuntimeException e)
{
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
System.out.print("Test " + numTotalTests + ": (" + operands[0] + " + " + operands[1] + ") ==> ");
if (sr.equals(results.get(i)))
{
System.out.println("[Passed]");
numPassedTests++;
}
else
System.out.println("[Failed]");
System.out.println(" Expected: " + results.get(i));
if (eMsg.equals("N/A"))
System.out.println(" Yours: " + sr + "\n");
else
System.out.println(" Yours: " + eMsg + "\n");
}
System.out.println("Total test cases: " + numTotalTests + "\nCorrect: " + numPassedTests + "\nWrong: " + (numTotalTests - numPassedTests));
}
catch (Exception e)
{
System.out.println("Error occurred: " + e.getMessage());
}
}
}