JAVA - Matching Parentheses (Must use a for loop) One application of stacks is t
ID: 3829784 • Letter: J
Question
JAVA - Matching Parentheses (Must use a for loop)
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<Character> s = new Stack<Character>();
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
import java.util.Scanner;
import java.util.Stack;
public class ParenMatch {
private static final char L_PAREN = '(';
private static final char R_PAREN = ')';
private static final char L_BRACE = '{';
private static final char R_BRACE = '}';
private static final char L_BRACKET = '[';
private static final char R_BRACKET = ']';
public static boolean isBalanced(String s) {
Stack<Character> stack = new Stack<Character>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i));
if (s.charAt(i) == L_PAREN) {
stack.push(L_PAREN);
}
else if (s.charAt(i) == L_BRACE) {
stack.push(L_BRACE);
}
else if (s.charAt(i) == L_BRACKET) {
stack.push(L_BRACKET);
}
else if (s.charAt(i) == R_PAREN) {
if (stack.isEmpty()) {
System.out.println("Error detected. " +
"More right paraenthesis '" + R_PAREN + "'. " +
"String processesed so far " + s.substring(0, i+1));
return false;
}
if (stack.pop() != L_PAREN) {
System.out.println("Error detected. " +
"More right paraenthesis '" + L_PAREN + "'. " +
"String processesed so far " + s.substring(0, i+1));
return false;
}
}
else if (s.charAt(i) == R_BRACE) {
if (stack.isEmpty()) {
System.out.println("Error detected. " +
"More right paraenthesis '" + R_BRACE + "'. " +
"String processesed so far " + s.substring(0, i+1));
return false;
}
if (stack.pop() != L_BRACE) {
System.out.println("Error detected. " +
"More right paraenthesis '" + L_BRACE + "'. " +
"String processesed so far " + s.substring(0, i+1));
return false;
}
}
else if (s.charAt(i) == R_BRACKET) {
if (stack.isEmpty()) {
System.out.println("Error detected. " +
"More right paraenthesis '" + R_BRACKET + "'. " +
"String processesed so far " + s.substring(0, i+1));
return false;
}
if (stack.pop() != L_BRACKET) {
System.out.println("Error detected. " +
"More right paraenthesis '" + L_BRACKET + "'. " +
"String processesed so far " + s.substring(0, i+1));
return false;
}
}
// ignore all other characters
}
boolean isBalanced = stack.isEmpty();
if (!isBalanced)
{
System.out.println("Not balanced after checking full string " + s);
System.out.println("has following paraenthesis extra ");
while(!stack.isEmpty())
System.out.print("'" + stack.pop() + "' ");
System.out.println();
}
return isBalanced;
}
public static void main(String[] args) {
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();
if(isBalanced(line))
{
System.out.println(line + " is balanced.");
}
scan.close();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.