Problem Link : http://www.codechef.com/problems/ONP
Solution :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Stack;
/**
*
* @author XCoder
*/
class TransformTheExpression_RPN_InfixToPostfix {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static PrintWriter pw = new PrintWriter(System.out);
public static int readIntLine() throws IOException {
return Integer.parseInt(br.readLine());
}
public static void main(String[] args) throws IOException {
Stack<Character> s = new Stack<Character>();
StringBuffer postfix = new StringBuffer();
int test = readIntLine();
while (test-- > 0) {
String str = br.readLine();
postfix.delete(0, postfix.length());
for (char c : str.toCharArray()) {
// System.out.println(c);
// System.out.println(postfix);
// System.out.println(s);
if (c == '(') {
s.push('(');
} else if (c == ')') {
while (!s.empty() && s.peek() != '(') {
postfix.append(s.pop());
}
s.pop(); //finally popping out the '('
} else if (isOper(c)) {
// System.out.println("is oper "+c);
while (!s.isEmpty() && precedence(s.peek(), c)) {
postfix.append(s.pop());
}
s.push(c);
} else {
postfix.append(c);
}
}
while (!s.empty()) {
postfix.append(s.pop());
}
System.out.println(postfix);
}
}
public static boolean precedence(char c1, char c2) {
char high[][] = {{'*', '+'}, {'*', '-'}, {'/', '+'}, {'/', '-'}, {'$', '*'}, {'$', '/'}, {'$', '+'}, {'$', '-'}, {'^', '*'}, {'^', '/'}, {'^', '+'}, {'^', '-'}};
char eq[][] = {{'*', '/'}, {'-', '+'}};
for (char[] arr : eq) {
if ((arr[0] == c1 && arr[1] == c2) || (arr[1] == c1 && arr[0] == c2)) {
return true;
}
}
for (char[] arr : high) {
if (arr[0] == c1 && arr[1] == c2) {
return true;
}
}
return false;
}
public static boolean isOper(char c) {
if (c == '+' || c == '*' || c == '-' || c == '/' || c == '$' || c == '^') {
return true;
} else {
return false;
}
}
}
No comments:
Post a Comment