Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //In the name of Allah
- /*
- Using the Stack and Recursive concept, develop a program to convert arithmetic expressions. The program should be able to:
- - Convert from infix to postfix
- - Convert infix to prefix
- The program must prompt user input an arithmetic infix expression for conversion to either prefix or postfix. The conversion option is wholly dependent to the user; either to postfix or prefix.
- ---
- Infix -> Postfix Rules:
- R1: Object operatorStack is empty
- R2: if operator, loop until the operator has been pushed onto the operatorStack
- -if the operatorStack is empty, or operator have higher precedence than the operator on top of the operatorStack,
- -push operator onto operatorStack
- -else
- -Pop the operatorStack and append that popped operator to the postfix string.
- R3: Once reach the end of input string
- -loop until operatorStack is empty
- -pop the operatorStack object and append that popped operator to the postfix string
- **Parentheses:
- if leftParentheses "(",
- pushed onto the operatorStack
- but precedence is lower than any other binary operator
- else if rightParenthese ")" is found
- operator object is repeatedly popped
- popped element appended to postfix string
- until operator on top is leftParentheses "("
- then that operator "(" is popped but not appended
- continue scanning the infix string
- Infix -> Prefix Rules:
- iNew algorithm
- 1: Reverse the input string
- 2: Examine the next element in the input
- 3. If it is operand, add it into the output string
- 4. If it is closing parenthesis, push it on stack
- 5. If it is an operator, then
- a. If stack.isEmpty, push operation on stack
- b. if the top of the stack is ")", push operator on stack
- c. if it has same or higher priority than the top of the stack, push it
- d. else pop the operator & add it to output string, repeat 5
- 6. If it is "(" pop operator and add them to string s until a ")" is encountered . POP and discard ")"
- 7. If there is more input go to step 2
- 8. If there is no more input, unstack the remaining operators and add them
- 9. Reverse the output string
- New algorithm
- 1. if operand push into operand stack
- 2. if operator
- a. if stack is empty or ch="(", push into operator stack
- b. if ")", CASE3 until reach "("
- c. else, CASE3
- 3. if endofexpression, CASE3 until operator stack empty
- 4. return the only operand in operandStack
- *Compile: javac 2009147897.java
- *Run: java PostfixPrefixApp
- Problems still arises1. Can't deal with expression with spaces in it E.g. [a + b]. Must use [a+b]
- 2. Program are too redundant at certain part: i++; and toPostfix(exp)
- 3. Thinking that this is more of the brute way rather than
- the inteligent way. Maybe can be simplified
- 4. Operators limited to * / + - %
- 5. Looping of the program cause unexpected result
- 6. toPrefix() is not correct.
- e.g: Didn't work for (a+b)+c+d, a+(c-h)/(b*d)
- */
- import java.util.*;
- class PostfixPrefixApp{
- /**Global Variables**************************************/
- private static Stack operatorStack= new Stack();
- private static Stack operandStack= new Stack();
- private static String postfix="";
- private static String prefix="";
- private static String temp="";
- private static int i=0; //use i to iterate through infix string [exp.charAt(i)]
- private static int menu=0;
- public static void main (String [] args){
- /**Local Variables***************************************/
- Scanner scan = new Scanner(System.in);
- String infix;
- /**Menu**************************************************/
- System.out.println ("\nChanging from infix to postfix or prefix notation.");
- System.out.println ("----------");
- System.out.println ("Menu");
- System.out.println ("----------");
- System.out.println ("1. Postfix");
- System.out.println ("2. Prefix");
- menu = scan.nextInt();
- /**Postfix***********************************************/
- if ( menu == 1){
- System.out.println ("Infix to Postfix");
- System.out.print ("Enter infix expression: ");
- infix = scan.next();
- postfix = toPostfix(infix);
- System.out.println("Postfix: "+ postfix);
- System.out.println ("----------");
- }
- /**Prefix************************************************/
- else if ( menu == 2){
- System.out.println ("Infix to Prefix");
- System.out.print ("Enter infix expression: ");
- infix = scan.next();// Storing the infix string
- infix=reverse(toPrefix(reverse(infix)));
- System.out.println("Prefix: "+infix);//display prefix string
- }
- /**Wrong input*******************************************/
- else {
- System.out.println ("Wrong input.");
- System.out.println ("----------");
- }
- System.exit(0);
- }
- /**toPostfix*********************************************/
- public static String toPostfix(String exp){
- if (exp.length()==i){
- /*
- for when the infix has finished being processed
- because iterate i for the usage of exp.charAt(i)
- */
- while (! operatorStack.isEmpty()){
- String temp = (String)operatorStack.peek();
- if (temp.charAt(0)!='(')//if there is "(" in the operatorStack
- postfix+=(String)operatorStack.pop();//pop all element into postfix string
- else
- operatorStack.pop();//removing "("
- }
- return postfix; //the last process of the recursion
- }
- else { //if the infix still being processed
- String ch = exp.substring(i,i+1);
- if (ch.charAt(0)==')'){//if opening parentheses "(", push it into stack
- operatorStack.push(ch);
- return redundantFunction(exp);// there are same processes that were simplified in this method instead. Refer "Problems arises"
- // or refer the method redundantFunction() below
- }
- else if (ch.charAt(0)=='('){
- /*
- if found closing parentheses ')'
- loop until reach '('
- append poped element of operatorStack into postfix string
- remove '(' from operatorStack
- */
- String topOfoperatorStack = (String)operatorStack.peek();
- while (! topOfoperatorStack.equals("(")){
- //String a=(String)operatorStack.pop();
- //System.out.println(a); //for testing process
- postfix+=operatorStack.pop();
- topOfoperatorStack = (String) operatorStack.peek();
- }
- operatorStack.pop();
- //String c= (String) operatorStack.pop();
- //System.out.println("c: "+c); //for testing if we correctly removing (
- return redundantFunction(exp);
- }
- else if (isOperand(ch)){
- /*
- if an operand a-zA-Z atau digit \\d
- directly appened to infix
- */
- postfix+=ch;
- return redundantFunction(exp);
- }
- else if (isOperator(ch)){
- /*
- if operators
- if empty
- directly push into operatorStack
- else
- see top of operatorStack
- if higher precendence
- directly push into operatorStack
- else
- pop topOfoperatorStack
- append it to postfix string
- push current operator into operatorStack
- */
- if (operatorStack.isEmpty()){
- operatorStack.push(ch);
- return redundantFunction(exp);
- }
- else {
- String topOfoperatorStack = (String)operatorStack.peek();
- if (precendence(ch) > precendence(topOfoperatorStack)){
- operatorStack.push(ch);
- return redundantFunction(exp);
- }
- else {
- postfix+=(String)operatorStack.pop();
- operatorStack.push(ch);
- return redundantFunction(exp);
- }
- }
- }
- else{
- //catching all other possible situation supposedly
- return redundantFunction(exp);
- }
- }
- }
- /**toPrefix**********************************************/
- private static String toPrefix(String exp){
- temp="";
- if (iprecendence( (String) operatorStack.peek() )) ){
- operatorStack.push(ch);
- }
- else{
- temp=CASE3();
- operandStack.push(temp);
- }
- }
- //System.out.println(ch);//testing
- return redundantFunction(exp);
- }
- else{
- while(! operatorStack.isEmpty()){
- temp=CASE3();
- operandStack.push(temp);
- }
- //System.out.println("Who is it? : "+operandStack.peek());//testing
- /*if (operandStack.isEmpty())//testing
- return "operandStack.isEmpty()";
- else*/
- return (String) operandStack.pop();
- }
- }
- /**isOperator********************************************/
- private static boolean isOperator(String ch){//method to check operator
- String operators = "*/%+-";
- if (operators.indexOf(ch) != -1)
- return true;
- else
- return false;
- }
- /**isOperand********************************************/
- private static boolean isOperand(String ch){//check if it is alphanumeric - method taken from outside sources
- if (ch.matches("[a-zA-Z]|\\d"))
- return true;
- else
- return false;
- }
- /**precedence********************************************/
- private static int precendence(String ch){//method that check the precendence of operator and return it
- //value 1 or 2
- String precendence2 = "*/%";
- String precendence1 = "+-";
- if (precendence2.indexOf(ch) != -1)
- return 2;
- else if (precendence1.indexOf(ch) != -1)
- return 1;
- else
- return 0;
- }
- /**redundantFunction********************************************/
- private static String redundantFunction(String exp){
- /*redundant processes
- need i to iterate through infix string while using recursion technique
- */
- i++;
- if (menu==1)
- return toPostfix(exp); //the recursion part
- else
- return toPrefix(exp); //the recursion part
- }
- /**reverse********************************************/
- private static String reverse(String exp){
- Stack tempString = new Stack();
- for (int index=0;index tempString.push( exp.charAt(index) );
- }
- exp="";
- while (! tempString.isEmpty() ){
- exp+= tempString.pop();
- }
- return exp;
- }
- private static String CASE3(){
- String opt="",oprn1="",oprn2="";
- opt += operatorStack.pop();
- oprn1 += operandStack.pop();
- if (operandStack.isEmpty())
- oprn2+="";
- else
- oprn2 += operandStack.pop();
- temp=opt+oprn2+oprn1;
- //System.out.println("Temp:"+temp);
- return temp;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement