Question

* the Algorithm:

* write a java program to convert infix to postfix

create(OpStk) OpStk.push("#") token = nextToken()
while (token != "#")
if (token is an operand)
append token to postfix expression
else if (token is "(") // Left paren - Start of sub-expr
OpStk.push( token )
else if (token is ")") // Right paren - End of sub-expr
pop operators off the stack and append to the postfix expression -
stop when you've popped a "("
else (token is an operator)
opr = OpStk.top()
while (StkPriority(opr) >= InPriority(token))
opr = OpStk.pop()
append opr to the postfix expression opr = OpStk.top()
endwhile
OpStk.push( token )
endif
token = nextToken()
endwhile
while (not OpStk.isEmpty())
opr = OpStk.pop()
append token to postfix expression
endwhile

Answer 1

/* Java implementation to convert infix expression to postfix*/
// Note that here we use Stack class for Stack operations
  
import java.util.Stack;
  
class Test
{
// A utility function to return precedence of a given operator
// Higher returned value means higher precedence
static int Prec(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;

case '*':
case '/':
return 2;

case '^':
return 3;
}
return -1;
}

// The main method that converts given infix expression
// to postfix expression.
static String infixToPostfix(String exp)
{
// initializing empty String for result
String result = new String("");
  
// initializing empty stack
Stack<Character> stack = new Stack<>();
  
for (int i = 0; i<exp.length(); ++i)
{
char c = exp.charAt(i);
  
// If the scanned character is an operand, add it to output.
if (Character.isLetterOrDigit(c))
result += c;

// If the scanned character is an '(', push it to the stack.
else if (c == '(')
stack.push(c);
  
// If the scanned character is an ')', pop and output from the stack
// until an '(' is encountered.
else if (c == ')')
{
while (!stack.isEmpty() && stack.peek() != '(')
result += stack.pop();
  
if (!stack.isEmpty() && stack.peek() != '(')
return "Invalid Expression"; // invalid expression   
else
stack.pop();
}
else // an operator is encountered
{
while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())){
if(stack.peek() == '(')
return "Invalid Expression";
result += stack.pop();
}
stack.push(c);
}

}

// pop all the operators from the stack
while (!stack.isEmpty()){
if(stack.peek() == '(')
return "Invalid Expression";
result += stack.pop();
}
return result;
}
  
// Driver method
public static void main(String[] args)
{
String exp = "a+b*(c^d-e)^(f+g*h)-i";
System.out.println(infixToPostfix(exp));
}
}