I need help with a stack-based algorithm that can convert an infix to its prefix equivalent using the Java programming language.

1. Please use the following three examples to test your program, please make sure the program can translate these infix expressions.
   1. Infix: A*((A-(B+C+D))*D-E*(F+C)), prefix: *A-*-A++BCDD*E+FC
   2. Infix: A-B+C*(A+B-C)*(C-D)$E*F, prefix: +-AB***C-+ABC$-CDEF
   3. Infix: (A+B)*(C-D)$E*F, prefix: **+AB$-CDEF

Please use this template.

template:

class charStack {

private final int STACKSIZE=100; private int top; private char [] items; /** * initialize the stack. * top is set to -1 to represent being empty. **/ public charStack() { items = new char[STACKSIZE]; top = -1; } /** * Checks to see if the stack is empty. * @return will return true if stack is empty. **/ public boolean empty() { if(top == -1) { return true; } else { return false; } } /** * Pops the top character on the stack. * @return char - the last character put into the stack. **/ public char pop() { if(empty()) { System.out.println("Stack underflow"); System.exit(1); } return items[top--]; } /** * Pushes the next character into the stack. * @param x - the character being pushed to the stack. **/ public void push(char x) { if(top == STACKSIZE - 1) { System.out.println("Stack Overflow"); System.exit(1); } items[++top] = x; } /** * Looks at the last character put into the stack. * @return char - the last character put into the stack. **/ public char peek() { if(empty()) { System.out.println("Stack fnderflow"); System.exit(1); } return items[top]; }

} public class prefix{

public static boolean isOperand(char symb){ if(symb=='+' || symb=='-' || symb=='*' || symb=='/' || symb=='$' || symb=='(' || symb==')'){ return false; }else{ return true; } }

public static String infix_to_prefix(String infix){ // TO DO: implement this method to convert and return // the prefix of the infix string // you should call the precedence() method } public static boolean precedence(char op1, char op2){ // TO DO: complete this method to compare for precedence // op2 is the operator on top of stack, op1 is the incoming operator int opcode1, opcode2; /* opcode for + or - is 1*/ /* opcode for * or / is 2 */ /* opcode for $ is 3 */ if(opcode1 >= opcode2) return true; else return false; } public static void main(String args[]){ String infix, preFix; System.out.println("Enter an infix string: ");

// TO DO: read the infix string from the keyboard

preFix = infix_to_prefix(infix); // method to convert System.out.println("The prefix is " + preFix); } }