One application of stacks is to keep track of things that must match up such as
ID: 3827943 • Letter: O
Question
One application of stacks is to keep track of things that must match up such as parentheses in an expression or braces in a program. In the case of parentheses when a left parenthesis is encountered it is pushed on the stack and when a right parenthesis is encountered its matching left parenthesis is popped from the stack. If the stack has no left parenthesis, that means the parentheses don’t match—there is an extra right parenthesis. If the expression ends with at least one left parenthesis still on the stack then again the parentheses don’t match—there is an extra left parenthesis.
File ParenMatch.java contains the skeleton of a program to match parentheses in an expression. It uses the Stack class provided by Java (in java.util). Complete the program by adding a loop to process the line entered to see if it contains matching parentheses. Just ignore characters that are neither left nor right parentheses. Your loop should stop as soon as it detects an error. After the loop print a message indicating what happened — the parentheses match, there are too many left parentheses, or there are too many right parentheses. Also print the part of the string up to where the error was detected.
// ********************************************************************
// ParenMatch.java
//
// Determines whether or not a string of characters contains
// matching left and right parentheses.
// ********************************************************************
import java.util.*;
import java.util.Scanner;
public class ParenMatch
{
public static void main (String[] args)
{
Stack s = new Stack();
String line; // the string of characters to be checked
Scanner scan = new Scanner(System.in);
System.out.println (" Parenthesis Matching");
System.out.print ("Enter a parenthesized expression: ");
line = scan.nextLine();
// loop to process the line one character at a time
// print the results
}
}
Explanation / Answer
// ParenMatch.java
import java.util.EmptyStackException;
import java.util.Stack;
/** Class to check for balanced parentheses.
* @author Aish
**/
public class ParenMatch {
// Constants
/** Set of opening parenthesis characters. */
private static final String OPEN = "([{";
/** Set of closing parenthesis characters, matches OPEN. */
private static final String CLOSE = ")]}";
public static boolean isBalanced(String expression) {
// Create an empty stack.
Stack<Character> s = new Stack<Character>();
boolean balanced = true;
try {
int index = 0;
while (index < expression.length()) {
char nextCh = expression.charAt(index);
if (isOpen(nextCh)) {
s.push(nextCh);
} else if (isClose(nextCh)) {
char topCh = (char) s.pop();
balanced =OPEN.indexOf(topCh) == CLOSE.indexOf(nextCh);
if(!balanced){
System.out.println("mismatch is "+topCh+" and "+nextCh);
return false;
}
}
index++;
}
} catch (EmptyStackException ex) {
System.out.println("Extra closing parenthesis");
return false;
}
if(!s.empty()){
System.out.println("extra opening paranthesis: "+s.toString());
return false;
}
return true;
}
/**
* Method to determine whether a character is one of the
* opening parentheses.
* @param ch Character to be tested
* @return true if ch is one of the opening parentheses
*/
private static boolean isOpen(char ch) {
return OPEN.indexOf(ch) > -1;
}
/**
* Method to determine whether a character is one of the
* closing parentheses.
* @param ch Character to be tested
* @return true if ch is one of the closing parentheses
*/
private static boolean isClose(char ch) {
return CLOSE.indexOf(ch) > -1;
}
public static void main(String[] args) {
String str = "{[public()]exmpty}";
if(isBalanced(str))
System.out.println("Balanced");
else
System.out.println("Not Balanced");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.