Notes

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author CJD & pahlavi5312
*/
import java.io.*;
public class FixInfix {

/*test input (p*(q+r/s))^(t-u-v)^w
* prefix ans:^^*p+q/rs--tuvw
* postfix ans: pqrs/+*tu-v-w^^
* infix: ((7+(9/3))-(2*4))
* prefix: -+7/93*24
* postfix: 793/+24*-
*/
public static String[] toCharArray(String inp){
String[] S = inp.split(" ");
return S;
}
public static double evalPrefix(String zzz){
String[] X = toCharArray(zzz);
iStack<Double> s = new iStack<Double>();
double a=0, b=0;
for (int i = X.length-1; i >= 0; i--) {
if(!isOperator(X[i])) s.push(Double.parseDouble(X[i]));
else{
a = s.pop();
b = s.pop();
s.push(eval(a, X[i], b));
}
}
return s.pop();
}
public static double evalPostfix(String zzz){
String[] X = toCharArray(zzz);
iStack<Double> s = new iStack<Double>();
double a= 0, b = 0;
for (int i = 0; i < X.length; i++) {
if(!isOperator(X[i])) s.push(Double.parseDouble(X[i]));
else{
b = s.pop();
a = s.pop();
s.push(eval(a, X[i], b));
}
}
return s.pop();
}
public static String toInfixfrPrefix(String zzz){
String[] X = toCharArray(zzz);
iStack<String> s = new iStack<String>();
String a="", b="";
for (int i = X.length-1; i >= 0; i--) {
if(!isOperator(X[i])) s.push(X[i]);
else{
a = s.pop();
b = s.pop();
s.push(concat(a, X[i], b));
}
}
return s.pop();
}
public static String toInfixfrPostfix(String zzz){
String[] X = toCharArray(zzz);
iStack<String> s = new iStack<String>();
String a= "", b = "";
for (int i = 0; i < X.length; i++) {
if(!isOperator(X[i])) s.push(X[i]);
else{
b = s.pop();
a = s.pop();
s.push(concat(a, X[i], b));
}
}
return s.pop();
}
public static String concat(String a, String o, String b){
StringBuffer sk = new StringBuffer("( ");
sk.append(a).append(" ").append(o).append(" ").append(b).append(" ").append(")").append(" ");
return sk.toString();
}
public static double eval(double x, String o, double y){
char c = o.charAt(0);
double w = 0;
switch(c){
case '+': w = x+y; break;
case '-': w = x-y; break;
case '*': w = x*y; break;
case '/': w = x/y; break;
case '^': w = Math.pow(x, y); break;
default: break;
}
return w;
}


public static void main(String[] args) {
System.out.println(toPostfix("X * ( ( 3 + 4 / Y ) - 2 )"));
System.out.println(toPrefix("X * ( ( 3 + 4 / Y ) - 2 )"));
System.out.println(toInfixfrPrefix("- + A B / C - D * E F"));
System.out.println(evalPrefix("- / * 9 8 6 - 7 + 2 1"));
System.out.println(evalPostfix("4 3 5 * 7 + 6 2 / - *"));
//System.out.println(!isOperator("10"));
}
public static String toPrefix(String zzz){
String[] X = toCharArray(zzz);
StringBuffer sk = new StringBuffer("");
iStack<String> rev = new iStack<String>();
iStack<String> optr = new iStack<String>();
for (int i = X.length-1; i >= 0 ; i--) {
if(!isOperator(X[i])) rev.push(X[i]);
else if (X[i] == "("){
while(optr.top() != ")")
rev.push(optr.pop());
if(optr.top() == ")") optr.pop();
}
else{
while(!optr.isEmpty() && !isEqualPos(optr.top(), X[i]) &&
getIncPrio(X[i]) < getInPrio(optr.top()))
if(X[i] == ")") break;
else rev.push(optr.pop());
optr.push(X[i]);
}
}
while(!optr.isEmpty()) rev.push(optr.pop());
while(!rev.isEmpty()) sk.append(rev.pop()).append(" ");
return sk.toString();
}
public static boolean isEqualPos(String a, String b){
return (getIncPrio(a) == getIncPrio(b) &&
getInPrio(a) == getInPrio(b));
}
public static String toPostfix(String zzz){
iStack<String> s = new iStack<String>();
String[] X = toCharArray(zzz);
StringBuffer sk = new StringBuffer("");
for (int i = 0; i < X.length; i++) {
if(!isOperator(X[i])){
sk.append(X[i]).append(" ");
//System.out.println(sk);
}
else if (X[i] == ")"){
while(s.top() != "(")
sk.append(s.pop()).append(" ");
if(s.top() == "(") s.pop();
}
else{
while(!s.isEmpty() &&
getIncPrio(X[i]) < getInPrio(s.top()))
sk.append(s.pop()).append(" ");
s.push(X[i]);
}
}
while(!s.isEmpty()){
if(s.top() == "(") s.pop();
else sk.append(s.pop()).append(" ");
}
return sk.toString();
}
public static boolean isOperator(String s){
return (s.equals("^") || s.equals("*") || s.equals("/")
|| s.equals("+") || s.equals("-") ||
s.equals("(") || s.equals(")"));
// switch(c){
// case '^': return true;
// case '*': return true;
// case '/': return true;
// case '+': return true;
// case '-': return true;
// case '(': return true;
// case ')': return true;
// default: return false;
// }
}
public static int getIncPrio(String s){
char c = s.charAt(0);
switch(c){
case '^': return 6;
case '*': return 3;
case '/': return 3;
case '+': return 1;
case '-': return 1;
case '(': return 9;
default: return -1;
}
}
public static int getInPrio(String s){
char c = s.charAt(0);
switch(c){
case '^': return 5;
case '*': return 4;
case '/': return 4;
case '+': return 2;
case '-': return 2;
case '(': return 0;
default: return -1;
}
}

}

class iStack<T> {
private int top = 0;
private final static int stackMax=100;
// highest index of stk array
private Object[] stk = new Object[stackMax+1];
//Elements must be cast back.
public iStack() { // constructor
}
// other methodsclear(s) // in Java, s is passed as the implied parameter “this”
public void clear(){
top = 0;
}

public boolean isEmpty(){
if (top == 0)
return true;
else
return false;
}

public void push(T el){
if (top == stackMax) // is stack full ?
System.out.print("Stack Push Overflow Error");
else top = top + 1;
stk[top] = el;
}

public T pop(){
if (isEmpty())
{System.out.print("Stack Pop Underflow Error");
return null;}
else
top = top-1;
return (T)stk[top + 1];
} // cast back if generic
public T top(){
if (isEmpty())
{System.out.print("Stack is Empty");
return null;}
else
return (T)stk[top]; // cast back if generic
}


}