Microsoft Interview Question
Team: Office
Country: United States
Interview Type: In-Person
does priority exist in these characters?
I assume the priority is { > ( > [ then we can use O(1) space to solve it
int a=0,b=0,c=0;
for (int i = 0; i < strlen(str): i++)
{
if(str[i]=='[') a++;
if(str[i]==']'){ a--; if(a<0) return false;}
if(str[i]=='(') {b++; if(a>0) return false;}
if(str[i]==')'){ b--; if(a>0||b<0) return false;}
if(str[i]=='{') {c++; if(a>0||b>0) return false;}
if(str[i]=='}') {c--; if(a>0||b>0||c<0) return false;}
}
if(a==0&&b==0&&c==0) return true;
return false;}
initially, the stack is empty, so when you encounter "}", your program will crash because the empty stack couldn't pop anything out
@Mihail.. speedmanics is right ..it will crash so u can just check before popping out element if it has any elements... also your second and third case of if statement are same
@zyfo2... your code is definitely better ... and if there is no priority in your code it becomes even simpler and you can just remove those checks and looks something like this
if(str[i]=='[') a++;
if(str[i]==']'){ a--; if(a<0) return false;}
if(str[i]=='(') {b++;}
if(str[i]==')'){ b--; if(b<0) return false;}
if(str[i]=='{') {c++; }
if(str[i]=='}') {c--; if(c<0) return false;}
Create 3 arrays for keeping the count of 3 different brackets.
Scan from left to right and increment count by 1 for { bracket and decrement by 1 for }.
In the end all three arrays should have 0 value.
your idea won't work for ({)} because at the end both of them would be 0 so according to you idea it is correct but actually it is incorrect
public class StringCompiler {
/**
* @param args
*/
public static void main(String[] args) {
System.out.println("Valid Pattern :" +check());
}
private static boolean check(){
Stack s = new Stack();
String pattern = "{{}}{}{}{}{}}";
for(int i=0;i<pattern.length();i++){
if( pattern.charAt(i)=='(' || pattern.charAt(i)=='{' || pattern.charAt(i)=='[' ){ // Check All Possible language patterns
s.push(pattern.charAt(i));
System.out.println("Pushing "+i+":"+pattern.charAt(i));
}else{
if(!s.empty()){
char c = (Character) s.pop();
if((c == '(' && pattern.charAt(i)==')') ||
(c == '[' && pattern.charAt(i)==']') ||
(c == '{' && pattern.charAt(i)=='}') ){
System.out.println("Poping "+i+":"+pattern.charAt(i));
}else{
return false;
}
}else {
return false;
}
}
}
if(s.empty())
return true;
return false;
}
}
bool Match(const string& str)
{
stack<char> s;
for (string::const_iterator it = str.begin();
it != str.end(); it++)
{
if (s.empty())
{
s.push(*it);
continue;
}
char c = s.top();
if ((*it == ']' && c == '[') ||
(*it == '}' && c == '{') ||
(*it == ')' && c == '('))
{
s.pop();
}
else{
s.push(*it);
}
}
return s.empty();
}
import java.util.Stack;
public class CheckBalance {
public static boolean check(String str) {
if (str == null || str.length() == 0) {
return true;
}
char[] strs = str.toCharArray();
Stack<Character> stack = new Stack<Character>();
for (char c : strs) {
if(!check(c)){
return false;
}
if(checkOpeningSymbol(c)){
stack.push(c);
}
if(checkEndingSymbol(c)){
stack.push(c);
if(stack.size() < 2)
return false;
char right = stack.pop();
char left = stack.pop();
if(!match(right,left)){
return false;
}
}
}
if(stack.isEmpty()){
return true;
}
return false;
}
private static boolean match(char right, char left) {
if(right == ')' && left == '(' ){
return true;
}
if(right == '}' && left == '{' ){
return true;
}
if(right == ']' && left == '[' ){
return true;
}
return false;
}
private static boolean check(char c) {
if (c == ')' || c == '}' || c == ']' || c == '{' || c == '['
|| c == '(') {
return true;
}
return false;
}
private static boolean checkEndingSymbol(Character peek) {
if (peek == ')' || peek == '}' || peek == ']') {
return true;
}
return false;
}
private static boolean checkOpeningSymbol(Character peek) {
if (peek == '{' || peek == '[' || peek == '(') {
return true;
}
return false;
}
public static void main(String[] args) {
// String str = "{()[]}";
// String str = "(({)})";
String str = "{())";
System.out.println(check(str));
}
}
#include<stdio.h>
#include<iostream>
using namespace std;
struct list
{
char ch;
struct list *next;
}*head=NULL;
char top()
{
if(!head)return '\0';
return head->ch;
}
struct list *pop(struct list *head)
{
head=head->next;
return head;
}
struct list *push(struct list *head,char ch)
{
struct list *temp;
char cc=top(),cd;
switch(ch)
{
case ']':
cd='[';
break;
case '}':
cd='{';
break;
case ')':
cd='(';
break;
default:
cd='a';
break;
}
if(cc==cd)
head=pop(head);
else{
if(!head)
{
head=new list;
head->ch=ch;
head->next=NULL;
}
else
{
temp=new list;
temp->ch=ch;
temp->next=head;
head=temp;
}
}
return head;
}
int main()
{
char str[100];
int i=0;
printf("enter the string:\n");
scanf("%s",str);
while(str[i]){head=push(head,str[i]);i++;}
if(!top())printf("\ncorrect");
else printf("\nincorrect");
return 0;
}
You can use a stack.
- Mihail Burduja January 24, 2013