Microsoft Interview Question
Software Engineer in TestsTeam: Server and tools in microsoft erp
Country: United States
Interview Type: In-Person
I wrote the following pseudo-code:
for each character in the string
push onto a stack, keeping track of the braces that are being used.
if you encounter any non-numeric characters, braces, or operands, return false
if you encounter a closing brace that has NOT has an opening brace, return false
if you encounter an opening brace following by an operand, return false
if you encounter a closing brace, pop off all values off the stack (until you reach opening)
if there is an operand by the closing brace, return false
if there is nothing between the opening & closing brace, return false
if you encounter two operands in a row, return false
once you pop off the opening brace, pop in any number.
package mytest;
import java.util.Stack;
/**
*
* @author Sun
*/
public class MyTest {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
String test="12*9-[(66+11)]*(77-22)";
System.out.println("Test equation: "+test);
System.out.println("Valid ? "+checkValid(test.toCharArray()));
}
static boolean checkValid(char[] equ){
int i,j=equ.length;
Stack<Character> astack=new Stack<>();
if(j==0)return false;
for(i=0;i<j;i++){
// System.out.println("?"+equ[i]);
if(isOpen(equ[i])){
if(!astack.isEmpty() && isNumber(astack.peek())){
return false;
}
astack.push(equ[i]);
}else if(isNumber(equ[i])){
astack.push(equ[i]);
}else if(isOp(equ[i])){
if(astack.isEmpty() || !isNumber(astack.peek())){
return false;
}
astack.push(equ[i]);
}else if(isClose(equ[i])){
if(astack.isEmpty() || !isNumber(astack.peek())){
return false;
}
while(!astack.isEmpty()){
char temp=astack.pop();
if(isOpen(temp)){
if(doMatch(temp,equ[i])){
break;
}else{
return false;//unexpected open
}
}else{
if(astack.isEmpty()){
return false;
}
}
}
astack.push('1');
}else{ //unexpected char
return false;
}
}
if(!astack.isEmpty() && !isNumber(astack.peek())) {
return false;
}
while(!astack.isEmpty()){
if(isOpen(astack.pop()))return false;
}
return true;
}
private static boolean isOpen(char c) {
if(c=='(' || c=='[')return true;
return false;
}
private static boolean isNumber(char c) {
if(c>='0' && c<='9')return true;
return false;
}
private static boolean isOp(char c) {
if(c=='+' || c=='-' || c=='*' || c=='/')return true;
return false;
}
private static boolean isClose(char c) {
if(c==')' || c==']')return true;
return false;
}
private static boolean doMatch(char temp, char c) {
if((temp=='(' && c==')')||(temp=='[' && c==']'))return true;
return false;
}
}
take 3 variables for each type of brackets initialize to 0, for open one do ++ for close one do -- and whenever the value become negative. Not a possible expression, and also after every operator there should not be an operator. after the end of expression check each variable is zero.
That's definitely not right. According to you, {2 + [4 + 3} + 1] is valid. You need to keep something like a stack and check if each parenthesis matches the previously-seen parenthesis. And checking the lack of two operators in a row is not strong enough. According to you, 2 + 6 3 2 1 (space between the numbers) is valid too.
Agree with Anonymous. given, {[3*(3+2)]+1} *5 .
first add, { [ 3 * ( 3 + 2 into the stack until you find a closing bracket . When you find ' )' pop elements out of the stack until you find a matching brace. check if '(' is a matching braces for ')' . If yes, continue iterating. Again ']' pop element until you find ']' . In any case, if the stack doesnt contain a matching brace or there are no elements to pop, return false. Correct me if I am wrong.
But how do we check if the operators are in the right place ?
You have to discuss with the interviewer as how the expression is going to be.
What kind of braces ( { [ ] } )
Whether it contains numbers/ characters
- 3a + 2b // legal , a3+b4 // illegal ?
What operators it can have ?
*,+,/,-,++,--,+-,+=,-=,*=,/=, ~ . Should you consider the operator precedence ?
by using stack, we can check whether parenthesis are matched or not. Same algo we can use to check the above valid math expression.
- siva.sai.2020 April 21, 2012Does any one has idea to solve short cut expression problems.
e.g :: (a+ (b+=c)) // valid
(a+(b=+c)) // invalid