30 points) 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 follow- ing strings have balanced parentheses: () (()()) ((())()) 1 The following strings do not have balanced parentheses: )( (() ())(()))()) We consider the empty string to have balanced parentheses, as there is no imbalance. The input to hasBalancedParantheses will always be a string only containing "(" or ")". Your task is to complete the has Balanced Parentheses() method. Note: this can be done both iteratively or recursively, but I be- lieve most people will find the iterative version much easier. Hint: There’s a pattern for how to determine if parentheses are balanced. Try to see if you can find that pattern first before coding this method up.
1 answer:
Answer:
The screenshot is attached below
Explanation:
The below program check balence of paranthesis using stack.
if the input charecter is ( then push to stack
if the input charecter is ) then pop top element and compair both elements for match.
Program:
public class Main
{
static class stack // create class for stack
{
int top=-1; // initialy stack is empty so top = -1
char items[] = new char[50]; // Create an array for stack to store stack elements
void push(char a) // Function push element to stack
{
if (top == 49) // chack stack is full ?
{
System.out.println("Stack full");
}
else
{
items[++top] = a; // increment the array index and store the element
}
}
char pop() // function to return the elements from stack
{
if (top == -1) // check the stack is empty
{
System.out.println("Empty stack");
return '\0';
}
else
{
char element = items[top]; // return the top element
top--; // Decrement the array index by one
return element;
}
}
boolean isEmpty() // Check the stack is empty or not
{
return (top == -1) ? true : false;
}
}
static boolean isMatch(char character1, char character2) // Check the input charecters are matching pairs or not
{
if (character1 == '(' && character2 == ')') // If they match return true
return true;
else
return false;
}
static boolean isBalanced(String parantheses) // check the input string is balenced or not
{
char[] exp = new char[parantheses.length()]; // Create a charecter array
for (int i = 0; i < parantheses.length(); i++) { // Convert the string parantheses to charecter array
exp[i] = parantheses.charAt(i);
}
stack st=new stack(); // Declare an empty character stack
for(int i=0;i<exp.length;i++)
{
if (exp[i] == '(')) // if input charecter is '(' push to stack
st.push(exp[i]);
if (exp[i] == ')') // if input charecter is ')' pop top element from stack
{
if (st.isEmpty())
{
return false;
}
else if ( !isMatch(st.pop(), exp[i]) ) // Call isMatch function
{
return false;
}
}
}
if (st.isEmpty())
return true; //balanced
else
{
return false; //not balanced
}
}
public static void main(String[] args)
{
System.out.println(isBalanced("()()()")); // Output true if string is balenced
}
}
Screenshot:
You might be interested in
Answer:
Explanation:
The code provided worked for the most part, it had some gramatical errors in when printing out the information as well as repeated values. I fixed and reorganized the printed information so that it is well formatted. The only thing that was missing from the code was the input validation to make sure that no negative values were passed. I added this within the getMonths() method so that it repeats the question until the user inputs a valid value. The program was tested and the output can be seen in the attached image below.
import java.io.*;
import java.util.*;
class Rainfall
{
Scanner in = new Scanner(System.in);
private int month = 12;
private double total = 0;
private double average;
private double standard_deviation;
private double largest;
private double smallest;
private double months[];
public Rainfall()
{
months = new double[12];
}
public void setMonths()
{
for(int n=1; n <= month; n++)
{
int answer = 0;
while (true) {
System.out.println("Enter the rainfall (in inches) for month #" + n + ":" );
answer = in.nextInt();
if (answer > 0) {
months[n-1] = answer;
break;
}
}
}
}
public void getTotal()
{
total = 0;
for(int i = 0; i < 12; i++)
{
total = total + months[i];
}
System.out.println("The total rainfall for the year is " + total);
}
public void getAverage()
{
average = total/12;
System.out.println("The average monthly rainfall is " + average);
}
public void getLargest()
{
double largest = 0;
int largeind = 0;
for(int i = 0; i < 12; i++)
{
if (months[i] > largest)
{
largest = months[i];
largeind = i;
}
}
System.out.println("The largest amount of rainfall was " + largest +
" inches in month " + (largeind + 1));
}
public void getSmallest()
{
double smallest = Double.MAX_VALUE;
int smallind = 0;
for(int n = 0; n < month; n++)
{
if (months[n] < smallest)
{
smallest = months[n];
smallind = n;
}
}
System.out.println("The smallest amount of rainfall was " + smallest +
" inches in month " + (smallind + 1));
}
public static void main(String[] args)
{
Rainfall r = new Rainfall();
r.setMonths();
r.getTotal();
r.getSmallest();
r.getLargest();
r.getAverage();
}
}
