Thread: prefix to infix

    #1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Location
    Ankara
    Posts
    8
    Rep Power
    0

    prefix to infix


    Does anybody has "prefix to infix" expression conversion algorithm ?
    If you have code segment it would be also very helpful.
    thanx in advance...
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Slovak republic
    Posts
    15
    Rep Power
    0

    i did it some time ago


    Once, I had to do it to school.
    I had expression in prefix and i had to print expression in infix and in postfix.
    Main idea was to representate expression as binary tree.
    i could look for my code, if you want to.
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Location
    Ankara
    Posts
    8
    Rep Power
    0

    yes of course


    it would be very good....
  6. #4
  7. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    heh, i had same assignment, solved the same way, i'll take a look as well if he cant find it.

    edit: argh, all i can find is my parse tree project. god i hated doing that project.
    Last edited by infamous41md; April 27th, 2003 at 09:35 PM.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Posts
    86
    Rep Power
    12
    here is an infix to postfix algorithm i made while studying first year of programming, not bad actually, made in java. it uses some extra classes i didnt paste in here, a stack and queue class, for pushing and popping the numbers, makes sense i think.

    Code:
    /*
     *|Program   : A program that converts infix to postfix notation and then evaluates it.
     *|Authors   : Bart Bobrowski & Adam Ludgate
     *|Date      : March 10, 2002
     *|Source(s) : Textbook
     *|Comment(s): Hmmmmmmm. Why do you have to use this program?
    */
    
    // ***YADA YADA***
    import tio.*;
    class Polish {
    	public static void main(String[] args) {
    // ***NOW THE FUN STUFF BEGINS...***
    
    	    try {
    
    		// ***YOU KNOW WHAT THESE ARE***
    		Deque queue = new Deque();
    		String part, a, b, c, d, e, f, g, r, s, t, u;
    		String[] whole = new String[100];
    		Stack scratch = new Stack();
    		int count, ob, i, j, m, n, o, p, q, v, w, z;
    		boolean error1 = false, error2 = false, error3 = false, operator = false, operand = false;
    		// ***END OF SOMETHING YOU KNOW***
    
    		// ***TITLE SCREEN***
    		System.out.println();
    		System.out.println("#####################################################################################################");
    		System.out.println("                            Infix::2::Postfix Converter / Calculator.");
    		System.out.println("");
    		System.out.println("Enter an equation, making sure you have a space between each character and ending with semi-colon.");
    		System.out.println("Example: ( 2 * ( 3 + 1 ) ) ; OR 4 / 2 ;");
    		System.out.println("#####################################################################################################");
    		System.out.println();
    		// ***END TITLE SCREEN***
    
    		// ***INPUT IS READ IN BY CONSOLE, AND SENT TO STRING ARRAY***
    		i = 0;
    		part = "";
    		while (!part.equals(";")) {
    			part = Console.in.readWord();
    			whole[i] = part;
    			i = i + 1;
    		}
    		// ***END READ IN***
    		
    		// ***MISC OPS***
    		System.out.println();
    		System.out.print("Postfix>> [");
    		ob = 0;
    		i = 0;
    		v = 0;
    		w = 0;
    		// ***END MISC***
    		
    		// ***CODE FOR CREATING THE POSTFIX NOTATION. (GOOD LUCK TRYING TO FOLLOW IT, HAHA.)***
    		while (!whole[i].equals(";")) {
    			if ((isBracket(whole[i]) || isOperand(whole[i]))) {
    				if (isOperand(whole[i])) {
    					queue.add(whole[i]); System.out.print(whole[i] + " "); w = w + 1; }
    				if (isBracket(whole[i])) {
    					if (whole[i].equals("("))
    						ob = ob + 1;
    					else {
    						for (j = 0; j < ob; j++) {
    							ob = ob - 1;
    							while (!scratch.empty()) {
    								s = (String)scratch.pop(); v = v - 1;
    								queue.add(s); System.out.print(s + " "); w = w + 1;	
    							}					
    						}
    					}
    				}
    			}
    			else if 
    				(isOperator(whole[i])) {
    					if (whole[i].equals("+")) {
    						if (!scratch.empty()) {
    							r = (String)scratch.top();
    							if ((r.equals("+")) || (r.equals("-"))) {
    								if (ob == 0) {
    									s = (String)scratch.pop(); v = v - 1;
    									scratch.push(whole[i]); v = v + 1;
    									queue.add(s); System.out.print(s + " "); w = w + 1;
    									}
    								else {
    									scratch.push(whole[i]); v = v + 1;
    									}
    								}
    							else if
    								((r.equals("*")) || (r.equals("/"))) {
    									if (ob == 0) {
    										scratch.push(whole[i]); v = v + 1;
    										}
    									else {
    										scratch.push(whole[i]); v = v + 1;
    										}
    							}
    						}
    						else {
    							scratch.push(whole[i]); v = v + 1;
    						}
    					}		
    					if (whole[i].equals("-")) {
    						if (!scratch.empty()) {
    							r = (String)scratch.top();
    							if ((r.equals("+")) || (r.equals("-"))) {
    								if (ob == 0) {
    									s = (String)scratch.pop(); v = v - 1;
    									scratch.push(whole[i]); v = v + 1;
    									queue.add(s); System.out.print(s + " "); w = w + 1;
    									}
    								else {
    									scratch.push(whole[i]); v = v + 1;
    									}
    								}
    							else if
    								((r.equals("*")) || (r.equals("/"))) {
    									if (ob == 0) {
    										scratch.push(whole[i]); v = v + 1;
    										}
    									else {
    										scratch.push(whole[i]); v = v + 1;
    										}
    							}
    						}
    						else {
    							scratch.push(whole[i]); v = v + 1;
    						}
    					}
    					if (whole[i].equals("*")) {
    						if (!scratch.empty()) {
    							r = (String)scratch.top();
    							if ((r.equals("+")) || (r.equals("-"))) {
    								scratch.push(whole[i]); v = v + 1;	
    							}
    							else if
    								((r.equals("*")) || (r.equals("/"))) {
    									if (ob == 0) {
    										s = (String)scratch.pop(); v = v - 1;
    										scratch.push(whole[i]); v = v + 1;
    										queue.add(s); System.out.print(s + " "); w = w + 1;
    										}
    									else {
    										scratch.push(whole[i]); v = v + 1;
    										}
    							}
    						}
    						else {
    							scratch.push(whole[i]); v = v + 1;
    						}
    					}
    					if (whole[i].equals("/")) {
    						if (!scratch.empty()) {
    							r = (String)scratch.top();
    							if ((r.equals("+")) || (r.equals("-"))) {
    								scratch.push(whole[i]); v = v + 1;	
    							}
    							else if
    								((r.equals("*")) || (r.equals("/"))) {
    									if (ob == 0) {
    										s = (String)scratch.pop(); v = v - 1;
    										scratch.push(whole[i]); v = v + 1;
    										queue.add(s); System.out.print(s + " "); w = w + 1;
    										}
    									else {
    										scratch.push(whole[i]); v = v + 1;
    										}
    							}
    						}
    						else {
    							scratch.push(whole[i]); v = v + 1;
    						}
    					}
    			}
    			i = i + 1;
    		}
    		// ***END OF POSTFIX CONVERSION CODE***
    	
    		// ***PRINTING OF POSTFIX FORM & TRANSFER TO DEQUE***
    		for (j = 0; j < v; j++) {
    			s = (String)scratch.pop();
    			queue.add(s); w = w + 1;
    			System.out.print(s + " ");
    		}	
    		System.out.print("]");
    		System.out.println();
    		// ***END OF POSTFIX STUFF***
    
    		// ***DEQUE ALGORITHM FOR CALCULATING POSTFIX NOTATION, LEAVING FINAL ANSWER IN QUEUE***
    		o = 0;
    		p = 0;
    		q = 0;
    		count = w;
    		while (count != 1) {
    			a = (String)queue.pop();
    			b = (String)queue.pop();
    			c = (String)queue.pop();
    			if (isOperator(c)) {
    				m = Integer.parseInt(a);
    				n = Integer.parseInt(b);
    				if (c.equals("+"))
    					o = m + n;
    				else if
    					(c.equals("-"))
    						o = m - n;
    				else if
    					(c.equals("*"))
    						o = m * n;
    				else if
    					(c.equals("/"))
    						o = m / n;
    				e = "" + o;
    				queue.add(e);
    				count = count - 2;
    				p = p + 1;
    			}
    			else if (!isOperator(c)) {
    				d = (String)queue.pop();
    				m = Integer.parseInt(b);
    				n = Integer.parseInt(c);
    				if (d.equals("+"))
    					o = m + n;
    				else if
    					(d.equals("-"))
    						o = m - n;
    				else if
    					(d.equals("*"))
    						o = m * n;
    				else if
    					(d.equals("/"))
    						o = m / n;
    				e = "" + o;
    				queue.add(a);
    				queue.add(e);
    				count = count - 2;
    				q = 2;
    			}
    			for (i = 0; i < (count - p - q); i++) {
    				f = (String)queue.pop();
    				queue.add(f);
    			}
    			p = 0;
    			q = 0;
    		}
    		// ***END DEQUE ALGORITHM***
    		
    		// ***PRINTING OF FINAL ANSWER***
    		while (!queue.empty()) {
    			String tempQ = (String)queue.pop();
    			System.out.print("Answer >> [" + tempQ + "]");
    		}
    		System.out.println();
    		System.out.println();
    		// ***END OF ANSWER PRINTING***
    	
    
    	    } catch (Exception e) { System.out.println("Error: Can't you type?!?"); }
    
    	}
    
    	// ***SHORTCUT FOR CHECKING VALIDITY OF OPERATOR***
    	static boolean isOperator(String s) {
    		return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    	}
    	// ***END OF OPRTR.***
    
    	// ***SHORTCUT FOR CHECKING VALIDITY OF OPERAND***
    	static boolean isOperand(String s) {
    		return s.equals("0") || s.equals("1") || s.equals("2") || s.equals("3") || s.equals("4") || s.equals("5") || s.equals("6") || s.equals("7") || s.equals("8") || s.equals("9");
    	}
    	// ***END OF OPRND.***
    
    	// ***SHORTCUT FOR CHECKING VALIDITY OF BRACKETS***
    	static boolean isBracket(String s) {
    		return s.equals("(") || s.equals(")");
    	}
    	// ***END OF BRCKT.***
    }
    // ***E.O.F.***
  10. #6
  11. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2003
    Posts
    1
    Rep Power
    0
    use the binary tree algorithm
    (use a binary tree data structure to store the expression)
    and from the tree you can use binary tree traversal algorithms
    to output in prefix,infix,postfix form
    (using preorder,inorder,postorder traversal)
    you can do it in just a couple lines with a recursive function

    the tree will look something like:

    &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp+
    &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp\
    &nbsp&nbsp&nbsp&nbsp&nbsp-&nbsp&nbsp&nbspc
    &nbsp&nbsp&nbspa&nbsp&nbspb&nbsp

    prefix = +-abc
    infix = ((a-b)+c)
    postfix = ab-c+

    anyways look up information on using binary trees
    in relation to pre/in/post -fix expressions
    Last edited by sh0e; May 19th, 2003 at 10:52 PM.

IMN logo majestic logo threadwatch logo seochat tools logo