T-Mobile Wi-Fi 2:23 AM oaklandcc.desire2learn.com Objectives To understand usage
ID: 3854880 • Letter: T
Question
T-Mobile Wi-Fi 2:23 AM oaklandcc.desire2learn.com Objectives To understand usage of Stacks better To perform and practice algorithm analysis Instructions This project is two-part: Programming with Stacks Algorithm Analysis Questions Programming with Stacks Write a program that uses Stacks to determine if a line written with parentheses is well-formed or not. This is a subtask that is similar to the techniques that compilers use to determine if you are missing (or have too many) curly braces or parentheses or brackets. The program should read the user input, and should push an open (when it is encountered, and perform a pop when a closed This way, if at the end of the program run, the stack is empty, then the line is well-formed. If the end of the input is reached and the stack is not empty, that means there were too many open If at any time, the program sees a closed parenthesis,), and the stack is empty already, then an exception will be thrown and this is an indicator that there are too many, or at least a misplaced, closed parenthesis. Either situation should cause the program to indicate it is not well formed. An example run might look like the following: Please input a set of parentheses re were too many open parentheses, Input is well-formed Another example run might look like the following: Please ieput a set of parentheses Serry, input is NOT well-formed 2. Algorithm Analysis The definition of Big O Let fin) and g(n) be functions mapping positive integers to positive real mbcn. We say that fim) is Ogl)) if there is a reall constant c0 and an integer constant N 2 1 such that: f(n)Sc g(n), for n2N Note that the constants e and n, are not nnigue. You just have to find a c and an N that satisfies the definition of Big O 3.1 Given a time function. T(n) = 2x: 4x 6. findExplanation / Answer
Here is the program for matching parenthesis along with output.
import java.util.Scanner;
import java.util.Stack;
public class CheckParenthesis {
public static void main(String[] args) {
String input;
Scanner scnr = new Scanner(System.in);
System.out.println("Please input a set of parenthesis: ");
input = scnr.next();
Stack<Character> stk = new Stack<Character>();
boolean valid = true;
char ch;
for(int i = 0; i < input.length() ; i++)
{
ch = input.charAt(i);
if(ch == '(')
stk.push(ch);
else if(ch == ')')
{
//if closing parenthesis is there , a matching open parenthesis should have been in stack,
//if not the input is not valid
if(stk.isEmpty())
{
valid = false;
break;
}
else
{
stk.pop();
}
}
}
//at the end of processing , stack should be empty, otherwise the input is not valid
if(!stk.isEmpty())
valid = false;
if(valid)
System.out.println("--> Input is well-formed.");
else
System.out.println("--> Sorry, input is NOT well-formed.");
}
}
output
Please input a set of parenthesis:
)(())(())
--> Sorry, input is NOT well-formed.
====
Please input a set of parenthesis:
()(())(())
--> Input is well-formed.
Answer for 3.3
There is a nested for loop inside another for loop. Both the loops execute n times each. So together , the println() line is executed n x n = n^2 times. So the code is of order O(n^2) .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.