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<Character> s = new Stack<Character>();

String line; // the string of characters to be checked

Scanner scan = new Scanner(System.in);

System.out.println ("\nParenthesis Matching");

System.out.print ("Enter a parenthesized expression: ");

line = scan.nextLine();

// loop to process the line one character at a time

// print the results

}

}

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// ParenMatch.java

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("\nParenthesis Matching");

            System.out.print("Enter a parenthesized expression: ");

            line = scan.nextLine();

            // denoting if there is an error in the expression

            boolean error = false;

            // string to store the string upto where the error was detected, if any

            String str = "";

            // loop to process the line one character at a time

            for (int i = 0; i < line.length(); i++) {

                  // appending current character to str

                  str += line.charAt(i);

                  // checking if char is '('

                  if (line.charAt(i) == '(') {

                        // pushing to stack

                        s.push('(');

                  }

                  // otherwise checking if it is ')'

                  else if (line.charAt(i) == ')') {

                        // if the stack is empty, there is no opening parentheses found

                        // for the current closing parentheses, means too many right

                        // parentheses

                        if (s.isEmpty()) {

                              System.out.println("Too many right parentheses");

                              error = true; // error detected

                              break; // end of loop

                        } else {

                              // removing top '(' from stack

                              s.pop();

                        }

                  }

            }

            // at the end if stack is not empty, it means that there are too many

            // left parentheses (that is left to be closed)

            if (!error && !s.isEmpty()) {

                  System.out.println("Too many left parentheses");

                  error = true;

            }

            // if no error is detected, displaying 'parentheses match'

            if (!error) {

                  System.out.println("parentheses match");

            } else {

                  // otherwise displaying the string upto which the error is detected

                  System.out.println("String upto where the error was detected: "

                              + str);

            }

      }

}

/*OUTPUT (different runs)*/

Parenthesis Matching

Enter a parenthesized expression: ((1+2)+(1/2))

parentheses match

Parenthesis Matching

Enter a parenthesized expression: ((1+2)+(1/2

Too many left parentheses

String upto where the error was detected: ((1+2)+(1/2

Parenthesis Matching

Enter a parenthesized expression: 1+2)+(1/2))

Too many right parentheses

String upto where the error was detected: 1+2)