Epic Systems Interview Question Software Developers
Country: United States
@ teargone08 thank you for you guys, here is my new code, the problem is I need to check whether the Queue is empty at last.
package EPIC;
import java.util.Stack;
public class BalancedString {
public static boolean isBalancedString(String S) {
Stack<Character> Q = new Stack<>();
for (int i = 0; i < S.length(); i++) {
char x = S.charAt(i);
if (x == '(' || x == '[' || x == '{') {
Q.add(x);
continue;
} else if (x == ')' && Q.pop() != '(') {
return false;
} else if (x == ']' && Q.pop() != '[') {
return false;
} else if (x == '}' && Q.pop() != '{') {
return false;
}
}
if(Q.isEmpty()){
return true;
}else{
return false;
}
}
public static void main(String[] args) {
System.out.println(isBalancedString("(a{A}b[c]"));
}
}
bool checkStringBalanced(string input) {
int brak = 0, curly = 0, sqr = 0;
char c;
std::stack<char> chars;
for (int i =0; i < input.size(); i++) {
switch (input[i]) {
case '{' :
curly++;
break;
case '}' :
curly--;
if (curly < 0)
return false;
break;
case '(' :
brak++;
break;
case ')' :
brak--;
if (brak < 0)
return false;
break;
case '[' :
sqr++;
break;
case ']' :
sqr--;
if (sqr < 0)
return false;
break;
default :
//Do none
break;
}
}
return !(curly || brak || sqr);
}
bool StringBalance(char* s){
std::vector<char> stack;
for(; *s; s++){
switch (*s){
case '(': case '[': case '{':
stack.push_back(*s);
break;
case ')': case ']': case '}': {
char match = (*s == ')') ? '(' :
(*s == '}') ? '{' : '[';
if (!stack.size() || (match != stack.back()))
return false;
stack.pop_back();
break;}
}
}
return !stack.size();
}
void main()
{
char* tests[] = {"[a(b{c}d)]", "[a(b{cd)}]", "[a(b{c}d)", "a(b{c}d)]"};
for (int i = 0; i < sizeof(tests)/sizeof(tests[0]); i++)
printf("%s->%d\n", tests[i], StringBalance(tests[i]));
getch();
}
private static boolean isBalanced(String s1) {
if (s1 == null || s1.length() == 0) {
return false;
}
char[] chars = s1.toCharArray();
Stack<Character> stack1 = new Stack<>(); // { e {
Stack<Character> stack2 = new Stack<>(); // [ e ]
Stack<Character> stack3 = new Stack<>(); // ( e )
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '{') {
if (!stack2.isEmpty() || !stack3.isEmpty()) {
return false;
}
stack1.push(chars[i]);
} else if (chars[i] == '[') {
if (!stack3.isEmpty()) {
return false;
}
stack2.push(chars[i]);
} else if (chars[i] == '(') {
stack3.push(chars[i]);
} else if (chars[i] == '}') {
if (!stack2.isEmpty() || !stack3.isEmpty()) {
return false;
}
if (stack1.isEmpty()) {
return false;
}
stack1.pop();
} else if (chars[i] == ']') {
if (!stack3.isEmpty()) {
return false;
}
if (stack2.isEmpty()) {
return false;
}
stack2.pop();
} else if (chars[i] == ')') {
if (stack3.isEmpty()) {
return false;
}
stack3.pop();
}
}
return true;
}
/*
Balance pairs of brackets/parens uses an array of m chars where the
start of the pair is at n and the match is at n+(m/2).
This implementation will ignore anything not in the pairs array, except
that if the first character of the passed in string is '^', "trace" will be set
and the consumptoin of the string.
If the max recursion level is exceeded, the process will bail. It is
currently set to 16.
Note that this can very easily be upgraded to do proper quote
processing (about eight more lines of code). Left as an exercise for the
reader.
usage:
./a.out string
Examples:
$ ./a.out "[[<<>>]()]"
string: [[<<>>]()]
balanced = true
$ ./a.out "^[[<<>>]()]"
string: ^[[<<>>]()]
level=0 start=^[[<<>>]()] s=^[[<<>>]()]
level=0 start=^[[<<>>]()] s=[[<<>>]()]
level=1 start=[[<<>>]()] s=[<<>>]()]
level=2 start=[<<>>]()] s=<<>>]()]
level=3 start=<<>>]()] s=<>>]()]
level=4 start=<>>]()] s=>>]()]
level=3 start=<<>>]()] s=>]()]
level=2 start=[<<>>]()] s=]()]
level=1 start=[[<<>>]()] s=()]
level=2 start=()] s=)]
level=1 start=[[<<>>]()] s=]
balanced = true
$ ./a.out "^[[<<>>]()"
string: ^[[<<>>]()
level=0 start=^[[<<>>]() s=^[[<<>>]()
level=0 start=^[[<<>>]() s=[[<<>>]()
level=1 start=[[<<>>]() s=[<<>>]()
level=2 start=[<<>>]() s=<<>>]()
level=3 start=<<>>]() s=<>>]()
level=4 start=<>>]() s=>>]()
level=3 start=<<>>]() s=>]()
level=2 start=[<<>>]() s=]()
level=1 start=[[<<>>]() s=()
level=2 start=() s=)
level=1 start=[[<<>>]() s=[[<<>>]()
level=2 start=() s=)
level=1 start=[[<<>>]() s=[[<<>>]()
balanced = false: Unbalanced start token: [ at position 1
$ ./a.out "[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]"
string: [[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]
Reached max recursion level: aborting.
balanced = false: Reached max recursion level 16: { at position 16
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int balance(char **ptr, const char *pairs, int npairs, int *level );
int max_level = 16;
int _trace = 0;
main(int argc, char **argv) {
int level = 0;
char *pairs="({[<)}]>";
char **s = &argv[1];
char *save = *s;;
int balanced = 0;
printf("string: %s\n",*s);
if (*save == '^') {
_trace = 1;
}
while (**s && balanced == 0) {
balanced = balance(s,pairs,strlen(pairs),&level);
}
printf("balanced = %s ",balanced == 0 ? "true\n" : "false: ");
if (balanced == -1) {
printf("Unbalanced end token: \"%c\" at position %ld\n",**s,*s-save);
} else if (balanced == 1) {
printf("Unbalanced start token: \"%c\" at position %ld\n",**s,*s-save);
} else if (balanced == 2) {
printf("Reached max recursion level %d: \"%c\" at position %ld\n",max_level,**s,*s-save);
}
}
int balance(char **s, const char *pairs, int npairs, int *level ) {
int i,k,balanced;
char *start = (*s);
balanced == 0;
if (*level > max_level) {
printf("Reached max recursion level: aborting.\n");
return 2;
}
if (*level) (*s)++;
k = (npairs)>>1;
while (**s) {
char *curr = *s;
if (_trace) printf("level=%d start=%s s=%s\n", *level, start, *s);
for (i=0; i<k; i++) {
int j = i+k;
if ( *curr == pairs[j] ) {
if ( *start != pairs[i] ) return -1;
(*level)--;
return 0;
} else if ( *curr == pairs[i] ) {
(*level)++;
balanced = balance(s, pairs, npairs, level);
if (balanced != 0) {
(*level)--;
return balanced;
}
break;
}
}
(*s)++;
}
if (!**s && *level !=0) {
*s = start;
if (_trace) printf("level=%d start=%s s=%s\n", *level, start, *s);
if (*level == -1) {
return -1;
}
return 1;
}
return 0;
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package stacks;
import java.util.Stack;
/**
*
* @author venkatramreddykunta
*/
public class BalancedString {
public static void main(String[] args) {
System.out.println("Balanced: "+isBalancedString("[[((Aiokf)sf23a)]]{}"));
}
private static boolean isBalancedString(String input) {
Stack<Character> balancedStack=new Stack<>();
int index=0;
char currentChar;
while(index<input.length()){
currentChar=input.charAt(index);
System.out.println("Index:"+index+", cur:"+currentChar+", stack: "+balancedStack);
if((currentChar>='0' && currentChar<='9') || (currentChar>='a' && currentChar<='z') || (currentChar>='A' && currentChar<='Z'))
{index++;continue;}
else if(currentChar=='(' || currentChar=='[' || currentChar=='{')
balancedStack.push(currentChar);
else if(!balancedStack.empty() && currentChar==')'){
if(balancedStack.peek()=='('){
balancedStack.pop(); // balanced till here
}else
return false;
}
else if(currentChar==']'){
if(!balancedStack.empty() && balancedStack.peek()=='['){
balancedStack.pop(); // balanced till here
}else
return false;
}
else if(currentChar=='}'){
if(!balancedStack.empty() && balancedStack.peek()=='{'){
balancedStack.pop(); // balanced till here
}else
return false;
}
else
return false;
index++;
}
if(balancedStack.empty())
return true;
else
return false;
}
}
public class balancedSparanthesis {
public static void main(String[] args)
{
String str = "(a{A}b[c])";
char[] arr = str.toCharArray();
Stack<Integer> first = new Stack<>();
Stack<Integer> second = new Stack<>();
Stack<Integer> third = new Stack<>();
boolean flag = true;
for(int i=0; i<str.length(); i++)
{
char tmp = str.charAt(i);
if(tmp=='(')
first.push(1);
else if(tmp==')')
{
if(first.isEmpty())
{
flag = false;
break;
}
else
first.pop();
}
if(tmp=='{')
second.push(1);
else if(tmp=='}')
{
if(second.isEmpty())
{
flag = false;
break;
}
else
second.pop();
}
if(tmp=='[')
third.push(1);
else if(tmp==']')
{
if(third.isEmpty())
{
flag = false;
break;
}
else
third.pop();
}
}
if(flag)
System.out.println("Balanced");
else
System.out.println("Not Balanced");
}
}
package balancedstring;
import java.util.Scanner;
public class BalancedString {
public static char[] stack = new char[10];
public static int top = 0;
public static void main(String[] args) {
int flag = 0;
System.out.print("Enter a balanced string");
Scanner in = new Scanner(System.in);
String input = in.next();
for(int i = 0;i<input.length();i++){
switch(input.charAt(i)){
case '{': top = top+1;
push(input.charAt(i));
break;
case '[':top = top+1;
push(input.charAt(i));
break;
case '(': top = top+1;
push(input.charAt(i));
break;
case '}': if(stack[top]=='{')
pop();
else{
//System.out.println("Not a balanced String");
flag = 1;
}
break;
case ']': if(stack[top]=='[')
pop();
else{
//System.out.println("Not a balanced String");
flag = 1;
}
break;
case ')': if(stack[top]=='(')
pop();
else{
//System.out.println("Not a balanced String");
flag = 1;
}
break;
default:
}
}
if(flag==0 && stack[top]==0){
System.out.print("A blanced string");
}
else
System.out.print("Unbalanced");
}
public static void push(char str){
stack[top] = str;
//System.out.println(stack[top]);
//top = top+1;
}
public static void pop(){
//System.out.println(stack[top]);
top = top - 1;
}
}
package balancedstring;
import java.util.Scanner;
public class BalancedString {
public static char[] stack = new char[10];
public static int top = 0;
public static void main(String[] args) {
int flag = 0;
System.out.print("Enter a balanced string");
Scanner in = new Scanner(System.in);
String input = in.next();
for(int i = 0;i<input.length();i++){
switch(input.charAt(i)){
case '{': top = top+1;
push(input.charAt(i));
break;
case '[':top = top+1;
push(input.charAt(i));
break;
case '(': top = top+1;
push(input.charAt(i));
break;
case '}': if(stack[top]=='{')
pop();
else{
//System.out.println("Not a balanced String");
flag = 1;
}
break;
case ']': if(stack[top]=='[')
pop();
else{
//System.out.println("Not a balanced String");
flag = 1;
}
break;
case ')': if(stack[top]=='(')
pop();
else{
//System.out.println("Not a balanced String");
flag = 1;
}
break;
default:
}
}
if(flag==0 && stack[top]==0){
System.out.print("A blanced string");
}
else
System.out.print("Unbalanced");
}
public static void push(char str){
stack[top] = str;
//System.out.println(stack[top]);
//top = top+1;
}
public static void pop(){
//System.out.println(stack[top]);
top = top - 1;
}
}
import java.util.Stack;
public class P22 {
private static boolean balancedCheck(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '[' || c == '(' || c == '{') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty() || stack.peek() != '(') {
return false;
}
stack.pop();
} else if (c == '}') {
if (stack.isEmpty() || stack.peek() != '{') {
return false;
}
stack.pop();
} else if (c == ']') {
if (stack.isEmpty() || stack.peek() != '[') {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(balancedCheck("{a[(b]]}"));
}
}
import java.util.Stack;
public class BalancedString {
public static void main(String[] args) {
String s = "{([)]}";
Stack<Character> st = new Stack<>();
for(int i =0; i< s.length() ;i++) {
char x = s.charAt(i);
if(x == '{' || x == '[' || x == '(') {
st.push(x);
continue;
} else if (x == '}' && st.peek() =='{') {
st.pop();
} else if (x == ')' && st.peek() =='(') {
st.pop();
} else if (x == ']' && st.peek() =='[') {
st.pop();
} else {
break;
}
}
if(st.isEmpty()) {
System.out.println("Balanced");
} else {
System.out.println("Not Balanced");
}
}
}
import java.util.Stack;
public class BalancedString {
public static void main(String [] args){
String given ="(a{A}b[c]";
System.out.println(given+" is balanced: "+isBalanced(given));
}
public static boolean isBalanced(String given){
Stack<Character> parens = new Stack<Character>();
for(int i=0;i<given.length();i++){
switch(given.charAt(i)){
case '{':
case '[':
case '(':
parens.push(given.charAt(i));
break;
case '}':
if(parens.size()!=0){
if(parens.pop()!='{'){
return false;
}
}else{
return false;
}
break;
case ']':
if(parens.size()!=0){
if(parens.pop()!='['){
return false;
}
}else{
return false;
}
break;
case ')':
if(parens.size()!=0){
if(parens.pop()!='('){
return false;
}
}else{
return false;
}
break;
}
}
if(parens.isEmpty())
return true;
else
return false;
}
}
public static bool IsBalanced(string text)
{
Stack<char> stack = new Stack<char>();
for (int i = 0; i < text.Length; i++)
{
char symbol = text[i];
if(symbol == '{' || symbol == '[' || symbol == '(')
{
stack.Push(symbol);
}
else if(symbol == '}' && (stack.Count == 0 || stack.Pop() != '{'))
{
return false;
}
else if (symbol == ')' && (stack.Count == 0 || stack.Pop() != '('))
{
return false;
}
else if (symbol == ']' && (stack.Count == 0 || stack.Pop() != '['))
{
return false;
}
}
if (stack.Count == 0)
{
return true;
}
else
{
return false;
}
}
static void Main(string[] args)
{
string text = "{a[sd[[sfs]dfdf(dfdf)]]}";
Console.WriteLine(IsBalanced(text));
Console.ReadLine();
}
- albertchenyu March 04, 2015package EPIC; import java.util.Stack; public class BalancedString { public static boolean isBalancedString(String S){ Stack<Character> Q = new Stack<>(); for (int i = 0; i < S.length(); i++) { char x = S.charAt(i); if( x == '(' || x == '[' || x == '{') { Q.add(x); continue; } else if (x == ')' && Q.pop() != '(') { return false; }else if(x == ']' && Q.pop() != '['){ return false; }else if(x == '}' && Q.pop() != '{'){ return false; } } return true; } public static void main(String[] args) { // System.out.println(isBalancedString("(as{ asdfasdf[asdfas]d} f)")); System.out.println(isBalancedString("(a[b]c)")); System.out.println(isBalancedString("(a[a{cb]c}c)")); } }