Microsoft Interview Question Software Engineer in Tests
Please don't be lazy and google it. For example here is the description of algo, I think writing the code will be quite simple
scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/index.htm
I tried to write this using shunting-yard in Java. Based on the code provided in wiki.
public class ShuntingYard {
public static StringBuilder convertToInfix(String input) {
//This is optional. Just removing whitespace in case.
StringBuilder sbuilder = new StringBuilder(input.length());
for(int i=0; i<input.length(); i++) {
if(input.charAt(i) != ' ') {
sbuilder.append(input.charAt(i));
}
}
input = sbuilder.toString();
System.out.println("After remove ws:" + input);
Queue<Character> queue = new Queue<Character>(input.length());
Stack<Character> stack = new Stack<Character>(input.length());
int c = 0;
while(c < input.length()) { //while there are tokens to be read
char in = input.charAt(c);
if(Character.isDigit(in)) { //if the token is numeric, enqueue
System.out.println("token is digit: " + in);
queue.enqueue(in);
}
else if(isFunction(in)) { //if the token is function, push to stack
System.out.println("token is function: " + in);
stack.push(in);
}
else if(in == ',') { //if input is comma
System.out.println("token is comma");
//Until the token at the top of stack is a left parenthesis, pop operators off the stack onto the queue.
//If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.
boolean leftParenthesisFound = false;
while(!stack.isEmpty()) {
Character popped = stack.pop();
if(popped == '(') {
leftParenthesisFound = true;
break;
}
else {
queue.enqueue(popped);
}
}
if(!leftParenthesisFound) {
System.out.println("ERROR: separator or parentheses mismatched!!");
return null;
}
}
else if(isOperator(in)) { //if the token o1 is an operator then:
System.out.println("token is operator: " + in);
//While there is an operator token o2 at the top of the stack, and
//either the o1 is left-associative and its precedence is less than or equal to that of o2,
//OR o1 is right-associative and its precedence is less than that of o2,
//POP o2 off the stack and enqueue to the queue.
//end While.
//PUSH o1 onto the stack.
while(!stack.isEmpty()) {
Character o2 = stack.peek();
if((isOperator(o2) && leftAssociativity(in) && operatorPrecedence(in) <= operatorPrecedence(o2)) ||
(isOperator(o2) && !leftAssociativity(in) && operatorPrecedence(in) < operatorPrecedence(o2))) {
o2 = stack.pop();
queue.enqueue(o2);
}
else {
break;
}
}
stack.push(in);
}
else if(in == '(') { //if the token is left parenthesis, push onto the stack
System.out.println("token is LP: " + in);
stack.push(in);
}
else if(in == ')') { //if the token is right parenthesis:
System.out.println("token is RP: " + in);
boolean rightParenthesisFound = false;
//Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the queue
while(!stack.isEmpty()) {
if(stack.peek() == '(') {
rightParenthesisFound = true;
break;
}
else {
queue.enqueue(stack.pop());
}
}
if(!rightParenthesisFound) {
System.out.println("ERROR: right parenthesis not found. Parentheses mismatched");
return null;
}
Character lp = stack.pop(); //pop left parenthesis but not to the queue
if(!stack.isEmpty()) {
if(isFunction(stack.peek())) { //if top of stack is function token, pop and enqueue
queue.enqueue(stack.pop());
}
}
}
else {
System.out.println("illegal token found: " + in);
return null;
}
c ++; //increment iterator
}//end while
//when token ran out but there are tokens in the stack,
//if the token on top of stack is a parenthesis, there are mismatched parentheses.
//POP the token onto the queue
while(!stack.isEmpty()) {
if(stack.peek() == '(' || stack.peek() == ')') {
System.out.println("ERROR: mismatched parenthesis found");
return null;
}
queue.enqueue(stack.pop());
}
StringBuilder sb = new StringBuilder(input.length());
queue.show();
while(!queue.isEmpty()) {
sb.append(queue.dequeue());
}
System.out.println(sb.toString());
return sb;
}//end convertToInfix
//
// operators
// precedence operators associativity
// 1 ! R to L
// 2 */ % L to R
// 3 + - L to R
// 4 = R to L
//
private static int operatorPrecedence(char c) {
switch(c) {
case '!':
return 4;
case '*': case '/': case '%':
return 3;
case '+': case '-':
return 2;
case '=':
return 1;
}
return 0;
}
//if the operator has left associativity, return true
private static boolean leftAssociativity(char c) {
switch(c) {
case '*': case '/': case '%': case '+': case '-':
return true;
case '=': case '!':
return false;
}
return false;
}
private static boolean isOperator(char c) {
if(c == '+' || c == '-' || c == '/' || c == '*' || c == '!' || c == '%' || c == '=' || c == '^') {
return true;
}
return false;
}
private static boolean isFunction(char c) {
if(c >= 'A' && c <= 'Z') {
System.out.println(c + " is function");
return true;
}
return false;
}
}
It can be easily implemented via three stacks. Let stack for brackets be B, stack for symbols be S and stack for operators be O. Consider the expression:
( (a+b) * (c - (d + e)) )
We shall assume that infix expression has proper brackets.
Now any time you encounter a '(' push S (start bracket) into B
Any time you encounter a symbol, push it in the symbol stack S
Any time you encounter an operator, push it in the operator stack O
Any time you encounter a ')' do the following:
- Pop the top two items representing '(' and ')' from B
- Pop the two symbols from S and top symbol from O
- Concatenate the top symbols and the operator and push it in S
Do the above until the brackets stack B is empty. Then the item in the symbols stack is the postfix expression.
Let's trace ( (a+b) * (c - (d + e)) )
1. [(] (a+b) * (c - (d + e)) ) B = ( S = O =
2. ( [(]a+b) * (c - (d + e)) ) B = (( S = O =
3. ( ([a]+b) * (c - (d + e)) ) B = (( S = a O =
4. ( (a[+]b) * (c - (d + e)) ) B = (( S = a O = +
5. ( (a+[b]) * (c - (d + e)) ) B = (( S = a b O = +
6. ( (a+b[)] * (c - (d + e)) ) B = ( S = ab+ O =
7. ( (a+b) [*] (c - (d + e)) ) B = ( S = ab+ O = *
8. ( (a+b) * [(]c - (d + e)) ) B = (( S = ab+ O = *
9. ( (a+b) * ([c] - (d + e)) ) B = (( S = ab+ c O = *
10. ( (a+b) * (c [-] (d + e)) ) B = (( S = ab+ c O = * -
11. ( (a+b) * (c - [(]d + e)) ) B = ((( S = ab+ c O = * -
12. ( (a+b) * (c - ([d] + e)) ) B = ((( S = ab+ c d O = * -
13. ( (a+b) * (c - (d [+] e)) ) B = ((( S = ab+ c d O = * - +
14. ( (a+b) * (c - (d + [e])) ) B = ((( S = ab+ c d e O = * - +
15. ( (a+b) * (c - (d + e[)]) ) B = (( S = ab+ c de+ O = * -
16. ( (a+b) * (c - (d + e)[)] ) B = ( S = ab+ cde+- O = *
17. ( (a+b) * (c - (d + e))[)] B = S = ab+cde+-* O =
Answer: ab+cde+-*
namespace InfixToPostfixString
{
class Program
{
public static Stack<char> opStack = new Stack<char>();
static void Main(string[] args)
{
Console.WriteLine(InfixToPostFix("(((A+B)+E)+(F*C))-D"));
Console.Read();
}
//little bit tricky
private static Boolean Precedence(char stackTop,char infix)
{
//here we are trying to find that if the stacktop is equal to preced[] value
char[] prec = { '(','/', '*', '+', '-',')' };
for (int i = 0; i < prec.Length; ++i)
{
if (prec[i] == stackTop)
return true;
if (prec[i] == infix)
return false;
}
return false;
}
public static StringBuilder InfixToPostFix(String infix)
{
StringBuilder postFix = new StringBuilder(); int i=0,j=0;
while (i < infix.Length)
{
if (IsThisAOperandChar(infix[i]))
{
postFix.Append(infix[i]);
}
else if(IsThisAOperatorChar(infix[i]))
{
while (opStack.Count != 0 && Precedence(opStack.Peek(), infix[i]))
{
if (opStack.Peek() == '(')
{
opStack.Pop();
break;
}
else postFix.Append(opStack.Pop());
}
if(infix[i]!=')')
opStack.Push(infix[i]);
}
else return null;
i++;
}
while (opStack.Count != 0)
{
if (opStack.Peek() == '(')
opStack.Pop();
else
postFix.Append(opStack.Pop());
}
return postFix;
}
public static bool IsThisAOperandChar(char input)
{
var asciiValue = Convert.ToInt16(input);
return ((asciiValue >= 65) && (asciiValue <= 90) || (asciiValue >= 97) && (asciiValue <= 122));
}
public static bool IsThisAOperatorChar(char input)
{
var asciiValue = Convert.ToInt16(input);
return ((asciiValue == 42) || (asciiValue == 43) || (asciiValue == 45) || (asciiValue == 47) || (asciiValue == 40) || (asciiValue == 41));
}
}
}
Quite simple by using two stacks. However should be careful during write this code during interview to avoid dummy mistakes...
- gevorgk June 07, 2010