Program To Implement a Node, Linked Stack, Stack Apps Using Java Programming Language Java Language Assignment Solution
- Instructions
- Requirements and Specifications
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());
}
}
}
Related Samples
Explore our free Data Structures and Algorithms assignment samples to enhance your understanding and improve your skills. Access a variety of examples that cover key concepts, providing you with valuable insights and practical knowledge to excel in your coursework. Start learning now!
Data Structures and Algorithms
Data Structures and Algorithms
Data Structures and Algorithms
Data Structures and Algorithms
Data Structures and Algorithms
Data Structures and Algorithms
Data Structures and Algorithms
Java
C++
Data Structures and Algorithms
Data Structures and Algorithms
Data Structures and Algorithms
Data Structures and Algorithms
Data Structures and Algorithms
Data Structures and Algorithms