JAVA. help in data structures(algorithm)

**jairoh_** · 03-09-2012, 02:14 PM

basically gamit ko ani ug tissue kai gadugo akong ilong.
btw, gamit ani katong concept na preFix(+ab), inFix(a+b), postFix(ab+) ,
input an inFix expression nya convert it into preFix or postFix.
Selection:
[1]Convert to preFix
[2]Convert to postix

2 (postFix ang gipili)

input inFix expression: (300+23)*(43-21)/(84+7) //kuha nani nako
Output in postFix: 300 23 + 43 21 - * 84 7 + /

input inFix expression: (60*4)+(43-21)-(44+7) //kuha nani nako
Output in postFix: 604 * 43 21 - + 44 7 + -

input inFix expression: (60*4)+(43-21)*(44+7)
Output in postFix: 60 4 * 43 21 - 44 7 + * +

input inFix expression: 12+(2-7) //kuha nani nako
Output in postFix: 12 2 7 - +

Selection:
[1]Convert to preFix
[2]Convert to postix

1 (preFix ang gipili)

input inFix expression: (300+23)*(43-21)/(84+7)
Output in preFix: / * + 300 23 - 43 21 + 84 7

input inFix expression: (60*4)+(43-21)-(44+7)
Output in preFix: - + * 60 4 - 43 21 + 44 7

input inFix expression: (60*4)+(43-21)*(44+7)
Output in preFix: + * 60 4 * - 43 21 + 44 7

input inFix expression: 12+(2-7)
Output in pretFix: + 12 - 2 7

ang paagi sa pag solve kai PMDAS pero di tanto kai same raman ang value sa multiplication/division or addition/subtraction, so left to right ang priority. maka solve ko ani manually pero sa paghimo nag codes, naglisud jud ko as in, mao nang ni post ko dri kai di pako ganahan mabuang, hahahaha.
here is my source code. (sample sa postfix ra akong nakuha(1st and second sample)). kanang sample uban, ako rai naghimo ana. wa pajud koi idea, tabang mga boss., hahaha boss stealthghost, superStar, Klave ug kinsa panang mga sweto na au. hehehe tnx daan.

Code:

import java.util.*;
public class Algo {
    
    private static Scanner in = new Scanner(System.in);
    private int selected=0,index1=0,index2=0,isTrue=0;
    private String expression="";
    private static List<Object> list = new ArrayList<Object>();
    private static List<Object> list2 = new ArrayList<Object>();
    private boolean digit,insideParentheses=false,tf=false;
    private String numbers = "", groupings="";
    private static PriorityQueue<Object> q = new PriorityQueue<Object>();
    private static Stack myStack = new Stack();
    private static Stack myStack2 = new Stack();
    
    public Algo(){
        Selection();
    }
    public void Selection(){
        try{
        System.out.println("Select Conversion: \n[1]PreFix \n[2]PostFix");
        this.selected = Integer.parseInt(in.nextLine());
        Selected(selected);
        }catch(Exception e){
            System.out.println("Invalid. Try again "+e.getMessage());
            Selection();
        }
    }
    public void Selected(int s){
        switch(s){
            case 1:
                askExpression();
                //PreFix();
                break;
            
            case 2:
                askExpression();
                postFixProcess();
                break;
            
            default:
                    System.out.println("Invalid. Try again");
                    Selection();
                break;
        }
    }
    public void askExpression(){
        System.out.println("\nInput Expression:");
        expression = in.nextLine();
        
        int size = expression.length();
        System.out.println("By one:");
        for(int x=0; x<size;x++){
            
            char c = expression.charAt(x);
            if(Character.isDigit(c)){
                this.numbers += c;
                digit = true;
                
            }else{
                if(digit==true){
                    list.add(numbers);
                }
                list.add(c);
                digit = false;
                this.numbers = "";
            }
           // System.out.println(numbers);
        }
        this.numbers = "";
        System.out.println(list);
   //======================================groupings    
        size = expression.length();
        System.out.println("By group:");
        for(int x=0; x<expression.length();x++){
            char c = expression.charAt(x);
            if(c=='('|c==')'){
                this.groupings += c;
                tf=true;
                if(c=='(')
                insideParentheses = true;
                else
                insideParentheses = false;
                
            }else if(insideParentheses==true){
                    this.groupings += c;
                    
            }else if(insideParentheses==false){
                if(tf==true)
                    list2.add(groupings);
                    list2.add(c);
                    groupings = "";
                    tf=false;
            }else
                list2.add(c);
            
        }
       System.out.println(list2);
            
    }
    public void postFixProcess(){
        System.out.println("Output:");
        for(int x=0; x<list.size();x++){
            if(list.get(x)=='('){
                myStack.push(list.get(x));
                insideParentheses = true;
            }else if(list.get(x)=='+'||list.get(x)=='-'||list.get(x)=='*'||list.get(x)=='/'){
                if(insideParentheses==true)
                myStack.add(list.get(x));
                if(insideParentheses==false)
                q.offer(list.get(x));    
            }else if(list.get(x)==')'){
                insideParentheses = false;
                System.out.print(myStack.pop()+" ");
                isTrue++;
               // insideParentheses = false; 
                /*
                if(insideParentheses==false)
                    System.out.print(myStack2.pop()+" ");
                insideParentheses = false;
                * 
                */
            }else
                System.out.print(list.get(x)+" ");
            if(isTrue==2){
                System.out.print(q.poll()+" ");
                isTrue = 0;
            }
            
            }
        if(isTrue==1)
            System.out.print(q.poll()+" ");
                //System.out.println("\n"+q);
        }
    
    
    public static void main(String args []){
        Algo a = new Algo();
    }
}

**moodsey211** · 03-09-2012, 04:14 PM

naabot na mo sa topic sa STACK? Basically manipulation ra ni sa stack. push and pop ka lang. naa ko codes ani sa una. pangitaon sa nako.

**stealthghost** · 03-09-2012, 04:21 PM

basahun sa nako ni...

Infix to Postfix Conversion

**jairoh_** · 03-09-2012, 05:14 PM

abot nami sa stacks. dpendi ra daw namu unsai gamiton na para sa collection. i'm using stack pud bya in my codes. hehehe.

**Klave** · 03-09-2012, 10:57 PM

ang input bah pwede multiple levels ang parenthesis?

Lingaw ni jairoh, hunahunaon sa nako.

First off, you can make the expression string into an EXPRESSION STACK first.

Meaning actual values na ang sulod per item sa stack.
(,+,-,/,*,) is one item.
a complete number is another item example. 300, 1, 5.

From this example.
(300+23)*(43-21)/(84+7)

This string array currently looks like.
(,3,0,0,+,2,3,),*,(,4,3,-,2,1,),/,(,8,4,+,7,)

Result for the expression stack should look like:
(,300,+,23,),*,(,43,-,21,),/,(,84,+,7,)

Anyways. naghunahuna pa ko sa uban.
But this is a good start, kay before nimo i postfix or prefix, kani man imong kanihanglan.

**jairoh_** · 03-10-2012, 08:30 AM

Originally Posted by Klave

ang input bah pwede multiple levels ang parenthesis?

Lingaw ni jairoh, hunahunaon sa nako.

First off, you can make the expression string into an EXPRESSION STACK first.

Meaning actual values na ang sulod per item sa stack.
(,+,-,/,*,) is one item.
a complete number is another item example. 300, 1, 5.

From this example.
(300+23)*(43-21)/(84+7)

This string array currently looks like.
(,3,0,0,+,2,3,),*,(,4,3,-,2,1,),/,(,8,4,+,7,)

Result for the expression stack should look like:
(,300,+,23,),*,(,43,-,21,),/,(,84,+,7,)

Anyways. naghunahuna pa ko sa uban.
But this is a good start, kay before nimo i postfix or prefix, kani man imong kanihanglan.

i've been thinking of that one bya bro. naa na sa akong codes sa taas.

mao ni output sakong codes

Code:

Select Conversion: 
[1]PreFix 
[2]PostFix
2

Input Expression:
(300+23)*(43-21)/(84+7)
By one:
[(, 300, +, 23, ), *, (, 43, -, 21, ), /, (, 84, +, 7, )]
By group:
[(300+23), *, (43-21), /]  //mao ni imo pasabot bro?grouped! pero kutob ras '/' ako,wa na mulahos
Output:
300 23 + 43 21 - * 84 7 + /

but what if ang input kai walai parentheses like 24/12+2*7, that makes my head spin.

**jairoh_** · 03-11-2012, 08:42 AM

u for this day! :P

**moodsey211** · 03-11-2012, 02:18 PM

bai, try this one:

Code:

import java.util.Stack;

public class Example 
{
	public static void main(String[] args) 
	{
		String normal = "(60*4)+(43-21)*(44+7)";
		Example ex = new Example();
		
		ex.ShowPostfix(normal);
	}

	public boolean IsHigherPrecedence(char ch, Stack<String> st)
	{
		if(st.empty()) {
			return true;
		}
		
		String tmp = st.peek();
		
		if(tmp.contentEquals("(")) {
			return true;
		} else {
			if((tmp.contentEquals("+") || tmp.contentEquals("-")) && (ch == '*' || ch == '/')) {
				return true;
			}
		}
		
		return false;
	}
	
	public void ShowPostfix(String arg) 
	{
		Stack<String> op = new Stack<String>();
		char ch;
		
		for(int i = 0; i < arg.length(); i++) {
			ch = arg.charAt(i);
			
			if(this.IsOperator(ch)) {
				if(ch == ')') {
					while(!op.peek().contentEquals("(")) {
						System.out.print(op.pop());
					}
					
					if(op.peek().contentEquals("(")) {
						op.pop();
					}
				} else if(ch == '(') {
					op.push(String.valueOf(ch));
				} else {
					if(!this.IsHigherPrecedence(ch, op)) {
						System.out.print(op.pop());
					} else {
						System.out.print(" ");
					}
					op.push(String.valueOf(ch));
				}
			} else {
				System.out.print(ch);
			}
		}
		
		while(!op.empty()) {
			System.out.print(op.pop());
		}
	}
	
	private boolean IsOperator(char ch)
	{
		switch(ch) {
			case '(':
			case ')':
			case '+':
			case '-':
			case '*':
			case '/':
				return true;
			default:
				return false;
		}
	}
}

**jairoh_** · 03-11-2012, 06:21 PM

Originally Posted by moodsey211

bai, try this one:

Code:

import java.util.Stack;

public class Example 
{
	public static void main(String[] args) 
	{
		String normal = "(60*4)+(43-21)*(44+7)";
		Example ex = new Example();
		
		ex.ShowPostfix(normal);
	}

	public boolean IsHigherPrecedence(char ch, Stack<String> st)
	{
		if(st.empty()) {
			return true;
		}
		
		String tmp = st.peek();
		
		if(tmp.contentEquals("(")) {
			return true;
		} else {
			if((tmp.contentEquals("+") || tmp.contentEquals("-")) && (ch == '*' || ch == '/')) {
				return true;
			}
		}
		
		return false;
	}
	
	public void ShowPostfix(String arg) 
	{
		Stack<String> op = new Stack<String>();
		char ch;
		
		for(int i = 0; i < arg.length(); i++) {
			ch = arg.charAt(i);
			
			if(this.IsOperator(ch)) {
				if(ch == ')') {
					while(!op.peek().contentEquals("(")) {
						System.out.print(op.pop());
					}
					
					if(op.peek().contentEquals("(")) {
						op.pop();
					}
				} else if(ch == '(') {
					op.push(String.valueOf(ch));
				} else {
					if(!this.IsHigherPrecedence(ch, op)) {
						System.out.print(op.pop());
					} else {
						System.out.print(" ");
					}
					op.push(String.valueOf(ch));
				}
			} else {
				System.out.print(ch);
			}
		}
		
		while(!op.empty()) {
			System.out.print(op.pop());
		}
	}
	
	private boolean IsOperator(char ch)
	{
		switch(ch) {
			case '(':
			case ')':
			case '+':
			case '-':
			case '*':
			case '/':
				return true;
			default:
				return false;
		}
	}
}

di man mao bro. hehehehe. tnx

**moodsey211** · 03-11-2012, 11:05 PM

Originally Posted by jairoh_

di man mao bro. hehehehe. tnx

Postfix ra na siya bai. mao na gigamit nako nga codes sa una.

Thread: JAVA. help in data structures(algorithm)

Thread Tools

Search Thread