CareerCup

enough material available for standard algorithm in web

while nothing remains to scan
- scan the first available element and enqueue it in queue
- scan the next available element and store it in a temporary variable 'temp'.
- scan the next available element and enqueue it in queue
- enqueue temp in queue

The algorithm for the conversion is as follows :
Scan the Infix string from left to right.
Initialise an empty stack.
If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack.
If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
Repeat this step till all the characters are scanned.
(After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.
Return the Postfix string.

Infix is essentially in-order traversal, if expressed in a binary tree. To express this in postfix, do LR-root traversal.

int GetOperatorPriority(char op)
{
    int priority = 0;

    switch (op)
    {
    case '+':
    case '-':
        priority = 0;
        break;
    case '*':
    case '/':
        priority = 1;
        break;
    default:
        throw invalid_argument("Invalid Operator");
    }

    return priority;
}

bool IsOperator(char ch)
{
    return 
        (ch == '+' ||
        ch == '-' ||
        ch == '*' ||
        ch == '/');
}

string InfixToPostfixExpression(string infixExpression)
{
    string postfixExpression = "";
    stack<char> operatorStack;

    for (char ch : infixExpression)
    {
        if (!IsOperator(ch))
        {
            postfixExpression += ch;
        }
        else
        {
            if (!operatorStack.empty())
            {
                while (!operatorStack.empty() && (GetOperatorPriority(operatorStack.top()) >= GetOperatorPriority(ch)))
                {
                    char opFromStack = operatorStack.top();
                    operatorStack.pop();

                    postfixExpression += opFromStack;
                }
            }

            operatorStack.push(ch);
        }
    }

    if (!operatorStack.empty())
    {
        char opFromStack = operatorStack.top();
        operatorStack.pop();
        postfixExpression += opFromStack;
    }

    return postfixExpression;
}

public String infixToPos(String infix){
Stack<Character> stack = new Stack<Character>();
StringBuffer pos = new StringBuffer();

for(int i = 0; i<infix.length(); i++){
char c = infix.charAt(i);
if(c!='+' && c!='-' && c!='*' && c!='/' ){
pos.append(c);
}else if(stack.empty()){
stack.push(c);
}else{
if(c == '*' || c == '/'){
System.out.println("Peek" + stack.peek());
while(stack.peek() == '*' || stack.peek() == '/'){
if(!stack.isEmpty()){
pos.append(stack.pop());
}
}
stack.push(c);
}else{
while(!stack.isEmpty()){
pos.append(stack.pop());
}
stack.push(c);
}
}
}

while(!stack.empty()){
pos.append(stack.pop());
}

return pos.toString();
}

while nothing remains to scan
- scan the first available element and enqueue it in queue
- scan the next available element and store it in a temporary variable 'temp'.
- scan the next available element and enqueue it in queue
- enqueue temp in queue