Hi, I've been having multiple problems with ONP - Transform the Expression, though I still wonder what's the matter with my code. I've probably read all the answers to similar topics and still nothing. I also tried different solutions suggested by many SPOJ members and randoms from the Internet (+ studied RPN before attempting to solve the problem). Moreover, it is still not clear to me whether or not to check the precedence.
The following code gets the answers correct at Ideaone and in eclipse.
(for precedence, I also tried with the suggestion that each operator has different priority, in this order +, -, *, /, ^)
Any ideas?
import java.util.*;
// ONP - Transform the Expression
// Reversed Polish Notation
class Main{
static String expression;
static char[] infix = new char [401];
static char[] postfix = new char[401];
static char[] stack = new char[401];
static int top = -1;
static void convertExpression(){
int len = expression.length();
for (int i=0; i<len; i++){
infix[i] = expression.charAt(i);
}
}
static boolean isOperator(char a){
if (a == '+' || a == '-' || a == '*' || a == '/' || a == '^')
return true;
else
return false;
}
static int precedence(char a){
if (a == '+' || a == '-')
return 1;
else if (a == '*' || a == '/')
return 2;
else if (a == '^')
return 3;
else
return 0;
}
static void push(char c){
top++;
stack[top] = c;
}
static char pop(){
char r = stack[top];
top--;
return r;
}
public static void main(String[] args) throws java.lang.Exception{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
sc.nextLine();
for (int i=0; i<t; i++){
expression = sc.nextLine();
convertExpression();
int a=0;
int len = expression.length();
for (int j=0; j<len; j++){
if (infix[j] == ' ')
continue;
else if (infix[j] == '(')
push(infix[j]);
else if (infix[j] == ')'){
char x;
while(top>=0 && stack[top]!='('){
x = pop();
postfix[a] = x;
a++;
}
x = pop();
}
else if (isOperator(infix[j])){
if (top>=0){
while (precedence(stack[top]) > precedence(infix[j])-1){
char x = pop();
postfix[a] = x;
a++;
push(infix[j]);
}
push(infix[j]);
}
else
push(infix[j]);
}
else{
postfix[a] = infix[j];
a++;
}
}
//if (top >= 0)
while (top>=0){
char x;
x = pop();
postfix[a] = x;
a++;
}
System.out.println(postfix);
postfix = new char[401];
}
sc.close();
}
}