Amazon Interview Question Quality Assurance Engineers
Country: United States
Interview Type: In-Person
If first character is ')', then n is 0 and this function return false.
This function is working correctly with ')))((('.
If we check only one type of parentheses such as '()', we do not need to use stack. Stack need to check valid with multiple type of parentheses and brackets such as '(){}[]'.
use stack, if it is "open" bracket push it into stack, else pop element from stack and check if it is "open" bracket, if yes - continue, else return false
Here is the code:
public class ValidExpr {
public static void main(String[] args) {
String expr = "()";
System.out.println(isValid(expr));
}
public static boolean isValid(String input) {
Stack<Character> stack = new Stack<>();
for (Character c : input.toCharArray()) {
if (c == '(') {
stack.push(c);
} else {
if (!stack.isEmpty()) {
char k = stack.pop();
if (k != '(') {
return false;
}
} else {
return false;
}
}
}
return stack.isEmpty();
}
}
I think if
!stack.isEmpty()
is true, we simply have to pop the topmost. No need to compare because the popped element will always be '(' since that's all that is ever pushed in.
def isvalid(s):
"""Check if the expression given in string 's' is a valid arithmetic
expression.
Eg: (())()) - Invalid expression, (()()) - Valid expression
>>> isvalid('(())())')
False
>>> isvalid('(()())')
True
"""
if not s:
return 0
ps = [] # stack of parentheses
for c in s:
if c in '()':
if ps and ps[-1] == '(' and c == ')':
ps.pop()
else:
ps.append(c)
return len(ps) == 0
if __name__ == '__main__':
import doctest
doctest.testmod()
package com.pocketlab.practice.algo.array;
import java.util.Stack;
/**
* How to find if a given expression is a valid arithmetic expression?
* Eg:(())()) - Invalid expression, (()()) - Valid expression
* @author user
*
*/
public class AMZ_ValidExp {
public static final String START_BRACKET = "(";
public static final String END_BRACKET = ")";
public static void main(String args[]) {
String exp = "(())())";
validate(exp);
exp = "(()())";
validate(exp);
}
public static boolean validate(String exp) {
Stack<String> stack = new Stack<String>();
boolean valid = true;
String[] arr = exp.split("");
for (String a : arr) {
if (a.equalsIgnoreCase(START_BRACKET)) {
stack.push(a);
} else {
if (stack.isEmpty()) {
valid = false;
break;
} else {
stack.pop();
}
}
}
if (!stack.isEmpty()) {
valid = false;
}
if (valid) {
System.out.println("Valid Express > " + exp);
} else {
System.out.println("Invalid Express > " + exp);
}
return false;
}
}
package com.pocketlab.practice.algo.array;
import java.util.Stack;
/**
* How to find if a given expression is a valid arithmetic expression?
* Eg:(())()) - Invalid expression, (()()) - Valid expression
* @author user
*
*/
public class AMZ_ValidExp {
public static final String START_BRACKET = "(";
public static final String END_BRACKET = ")";
public static void main(String args[]) {
String exp = "(())())";
validate(exp);
exp = "(()())";
validate(exp);
}
public static boolean validate(String exp) {
Stack<String> stack = new Stack<String>();
boolean valid = true;
String[] arr = exp.split("");
for (String a : arr) {
if (a.equalsIgnoreCase(START_BRACKET)) {
stack.push(a);
} else {
if (stack.isEmpty()) {
valid = false;
break;
} else {
stack.pop();
}
}
}
if (!stack.isEmpty()) {
valid = false;
}
if (valid) {
System.out.println("Valid Express > " + exp);
} else {
System.out.println("Invalid Express > " + exp);
}
return false;
}
}
import java.io.*;
public class Solution {
static String findValidExpression(String arr){
int count = 0;
for(char s : arr.toCharArray()){
if(s=='('){
count++;
}
else{
count--;
}
if(count<0){
return "invalid";
}
}
return "valid";
}
public static void main(String[] arg) throws IOException{
System.out.println("Enter the string ");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String a=br.readLine();
System.out.println("Expression is "+findValidExpression(a));
}
}
#include<stdio.h>
#include<stdlib.h>
int stack[50];
int top=-1;
void push(char elem)
{
stack[++top]=elem;
}
char pop()
{
char elem;
elem=stack[top--];
return elem;
}
int main()
{
char str[50];
int i=0,flag=0;
char ch,elem;
printf("enter expression");
scanf("%s",str);
while(str[i]!='\0')
{
if(str[i]=='('||str[i]=='{'||str[i]=='[')
push(str[i]);
i++;
if(str[i]==')'||str[i]=='}'||str[i]==']')
{
elem=pop();
if(str[i]==')'&&elem=='(')
flag=1;
else
flag=0;
if(str[i]=='}'&&elem=='{')
flag=1;
else
flag=0;
if(str[i]==']'&&elem=='[')
flag=1;
else
flag=0;
}
}
if(flag=1&&top<0)
printf("properly nested");
else
printf("not properly nested");
return 0;
}
public class Validation {
static char open= '(';
static char close = ')' ;
public static boolean isValid(byte[] expr) {
int sum = 0;
for(int i=0; i<expr.length; i++) {
if(expr[i] == open) {
sum++;
}
else if (expr[i] == close){
sum--;
if (sum < 0) {
return false;}
}
}
if (sum == 0) {
return true;}
else {
return false;}
}
public static void main(String[] args) {
String expr = "())(";
if (isValid(expr.getBytes()) == true) {
System.out.println("Valid Expression");
}
else {
System.out.println("Invalid Expression");
}
}
}
public static void expressionChecker(String s)
{
//String s="()()()(((()))))()()";
int left=0;
if(s.length()%2==0)
{
if(s.charAt(0)==')')
{
System.out.println("invalid expression");
}
else
{
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)=='(')
{
left++;
}
if(s.charAt(i)==')'&& left>0)
{
left--;
}
}
if(left==0)
{
System.out.println("valid erxpression");
}
else
{
System.out.println("Invalid erxpression");
}
}
}
else
{
System.out.println("invalid expression");
}
}
public static void expressionChecker(String s)
{
//String s="()()()(((()))))()()";
int left=0;
if(s.length()%2==0)
{
if(s.charAt(0)==')')
{
System.out.println("invalid expression");
}
else
{
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)=='(')
{
left++;
}
if(s.charAt(i)==')'&& left>0)
{
left--;
}
}
if(left==0)
{
System.out.println("valid erxpression");
}
else
{
System.out.println("Invalid erxpression");
}
}
}
else
{
System.out.println("invalid expression");
}
}
public static void main(String[] args) {
String s = "()()()";
String[] arrS = s.split("");
int count = 0;
ArrayList<String> al = new ArrayList<>(Arrays.asList(arrS));
for(int i=0; i<al.size(); i++) {
if(al.get(i).equals("(")) {
al.remove(i);
count++;
}
}
if(al.size()==count) {
System.out.println("Valid arithmetic expression");
} else {
System.out.println("Not an arithmetic expression");
}
}
String test ="(())()(())";
HashMap<Character, Integer> h= new HashMap<Character,Integer>();
for(int i=0;i<test.length();i++)
{
if(!h.containsKey(test.charAt(i)))
h.put(test.charAt(i), 1);
else
h.put(test.charAt(i), h.get(test.charAt(i))+1);
}
int firstcount=0,secondcount=0;
for(Map.Entry<Character,Integer> m : h.entrySet() )
{
if(m.getKey()=='(')
{
firstcount=m.getValue();
}
else if(m.getKey()==')')
secondcount=m.getValue();
}
if(firstcount==secondcount)
System.out.println("valid expression");
else
System.out.println("Invalid Expression");
c++, implementation
- kyduke October 24, 2015bool validParenthesis(string str) { int i, n; i = 0; n = 0; while (i < str.size()) { if (str[i] == '(') { n++; } else if (str[i] == ')') { if (n == 0) return false; n--; } i++; } return (n == 0); }