Question

Suppose you are given a string containing only the characters ( and ). In this problem, you will write a function to determine whether the string has balanced parentheses. Your algorithm should use no more than O (1) space beyond the input; any algorithms that use space not in O (1) will receive half credit at most. Any solutions that always return true (or always return false) or otherwise try to game the distribution of test cases will receive zero credit.

Balanced parentheses means that every open parenthesis has exactly one close parenthesis corresponding to it and vice versa, and that for each pair the opening parenthesis precedes the closed parenthesis. The following strings have balanced parentheses: () (()()) ((())())

The following strings do not have balanced parentheses: )( (() ())(()))())

We consider the empty string to have balanced parentheses, as there is no imbalance. Your program should accept as input a single string containing only the characters ) and (, and output a single line stating true or false .

The functionality for reading and printing answers is written in the class; your task is to complete the hasBalancedParentheses() method.

PLEASE START WITH THIS CODE

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
  
// Read the input string
String input = sc.nextLine();
  
BalancedParentheses bp = new BalancedParentheses();
// Print whether the string has balanced parentheses
System.out.println(bp.hasBalancedParentheses(input));
}
}

class BalancedParentheses {
public boolean hasBalancedParentheses(String input) {
// Remove this and implement code
throw new UnsupportedOperationException();
}
}

Answer 1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

// Read the input string
        String input = sc.nextLine();

        BalancedParentheses bp = new BalancedParentheses();
// Print whether the string has balanced parentheses
        System.out.println(bp.hasBalancedParentheses(input));
    }
}

class BalancedParentheses {
    public boolean hasBalancedParentheses(String input) {
        int count = 0;
        char ch;
        for (int i = 0; i < input.length(); i++) {
            ch = input.charAt(i);
            if (ch == '(') {
                count++;
            } else if (ch == ')') {
                if (count == 0) {
                    return false;
                }
                count--;
            }
        }
        return count == 0;
    }
}