This Java program is to implement graph structured stack. In computer science, a graph-structured stack is a directed acyclic graph where each directed path represents a stack. The graph-structured stack is an essential part of Tomita’s algorithm, where it replaces the usual stack of a pushdown automaton. This allows the algorithm to encode the nondeterministic choices in parsing an ambiguous grammar, sometimes with greater efficiency.
Here is the source code of the Java program to implement graph structured stack. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.ArrayList; import java.util.Iterator; import java.util.Scanner; import java.util.Stack; public class GraphStructuredStack { private ArrayList<Stack<Integer>> stackList; private Stack<Integer> stack; private int numberOfNodes; private int adjacencyMatrix[][]; private int[] parent; public GraphStructuredStack() { stackList = new ArrayList<Stack<Integer>>(); stack = new Stack<Integer>(); } public void graphStructuredStack(int adjacencyMatrix[][],int source,int bottomNode) { boolean stackFound = false; this.numberOfNodes = adjacencyMatrix.length - 1; this.adjacencyMatrix = new int[numberOfNodes + 1][numberOfNodes +1]; this.parent = new int[numberOfNodes+ 1]; for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++) { for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++) { this.adjacencyMatrix[sourceVertex][destinationVertex] = adjacencyMatrix[sourceVertex][destinationVertex]; } } stack.push(source); int element, destination; while (!stack.isEmpty()) { element = stack.peek(); destination = 1; while (destination <= numberOfNodes) { if (this.adjacencyMatrix[element][destination] == 1) { stack.push(destination); parent[destination] = element; this.adjacencyMatrix[element][destination] = 0; if (destination == bottomNode) { stackFound = true; break; } element = destination; destination = 1; continue; } destination++; } if (stackFound) { Stack<Integer> istack = new Stack<Integer>(); for (int node = bottomNode; node != source; node = parent[node]) { istack.push(node); } istack.push(source); stackList.add(istack); stackFound = false; } stack.pop(); } Iterator<Stack<Integer>> iterator = stackList.iterator(); while (iterator.hasNext()) { Stack<Integer> stack = iterator.next(); Iterator<Integer> stckitr = stack.iterator(); while (stckitr.hasNext()) { System.out.print(stckitr.next() +"\t"); } System.out.println(); } } public static void main(String...arg) { int adjacencyMatrix[][]; int numberofnodes; int source, bottom; Scanner scanner = new Scanner(System.in); System.out.println("enter the number of nodes"); numberofnodes = scanner.nextInt(); adjacencyMatrix = new int[numberofnodes + 1] [numberofnodes + 1]; System.out.println("enter the graph matrix"); for (int sourceVertex = 1; sourceVertex <= numberofnodes; sourceVertex++) { for (int destinationVertex = 1; destinationVertex <= numberofnodes; destinationVertex++) { adjacencyMatrix[sourceVertex][destinationVertex] = scanner.nextInt(); } } System.out.println("enter the source node"); source = scanner.nextInt(); System.out.println("enter the bottom node"); bottom = scanner.nextInt(); System.out.println("the stacks are"); GraphStructuredStack graphStructuredStack = new GraphStructuredStack(); graphStructuredStack.graphStructuredStack(adjacencyMatrix, source, bottom); scanner.close(); } }
$javac GraphStructuredStack.java $java GraphStructuredStack enter the number of nodes 6 enter the graph matrix 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 enter the source node 6 enter the bottom node 1 the stacks are 1 2 4 5 6 1 3 4 5 6
Related posts:
Java – Write an InputStream to a File
Giới thiệu thư viện Apache Commons Chain
Spring Boot - Admin Client
Java List UnsupportedOperationException
Using Optional with Jackson
Immutable Map Implementations in Java
Guide to @ConfigurationProperties in Spring Boot
Guide to Spring Cloud Kubernetes
Introduction to the Java NIO2 File API
A Guide to the ViewResolver in Spring MVC
Spring Boot - Tomcat Deployment
Java Program to Perform Matrix Multiplication
A Guide to System.exit()
Comparing Objects in Java
Send email with JavaMail
Java Program to Implement Sorted Vector
Checked and Unchecked Exceptions in Java
Guide to the Java TransferQueue
Abstract class và Interface trong Java
Spring Boot - Enabling HTTPS
Java Program to Implement Fisher-Yates Algorithm for Array Shuffling
Java Program to Implement Leftist Heap
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Java – Write a Reader to File
Quick Guide to Spring Controllers
Handling Errors in Spring WebFlux
Configure a Spring Boot Web Application
Java Program to Find a Good Feedback Vertex Set
Fixing 401s with CORS Preflights and Spring Security
Deque và ArrayDeque trong Java
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to Perform Searching Using Self-Organizing Lists