Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 10 of 10

Thread: Using Stack Data Type to Solve an Infix Expression

  1. #1
    Junior Member
    Join Date
    Oct 2011
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Using Stack Data Type to Solve an Infix Expression

    Hello! I have been given the assignment to use two ( 2 ) stacks to evaluate an infix expression. I cannot switch to postfix or prefix, then solve. It has to be a direct computation. I have been working on this for around 5 hours and cannot figure out why my code isn't working. When I run the program and type in an expression.... nothing happens. No errors, just no output. Any help pushing me in the right direction would be greatly appreciated. THANKS!

    import java.util.Scanner;
    import java.util.Stack;
    import java.util.regex.Pattern;
     
     
    public class InfixEvaluation {
    	public static double evalz(String expression) {
     
    	Scanner          console   = new Scanner(expression);
    	Stack<Character> opStack   = new Stack<Character>();
    	Stack<Double>    valStack  = new Stack<Double>();
     
     
     
    	String operator;
    	char   topOperator;
    	char   first;
    	double operandTwo;
    	double operandOne;
    	double result;
    	double next;
     
    	while(console.hasNext( )) {
     
    	}
    	 if (console.hasNextDouble()) {
    	    	next = console.nextDouble();
    	    	valStack.push(next);
     
       } else {
    	   operator  = console.next();
           first = operator.charAt(0);
     
    	 switch (first) {
     
    	 case '^': 
    		 opStack.push(first);
    	 	break;
    	 case '+':
    	 case '-':
    	 case '*':
    	 case '/':
    		 while (!opStack.isEmpty() 
    				 && getPriority(first) <= getPriority(opStack.peek())) {
    			 // Execute operator at top of opStack
    			 topOperator = opStack.pop();
    			 operandTwo  = valStack.pop();
    			 operandOne  = valStack.pop();
     
    			 if      (topOperator == '*')    result = operandOne * operandTwo;
    			 else if (topOperator == '+')    result = operandOne + operandTwo;
    			 else if (topOperator == '-')    result = operandOne - operandTwo;
    			 else
    			       throw new InfixException("Illegal symbol: " + topOperator);
     
    			 valStack.push(result);			 
    		 }
    		 opStack.push(first);
    		 break;
    	 case '(':
    		 opStack.push(first);
    		 break;
    	 case ')': // Stack is not empty if infix expression is valid
    		 topOperator = opStack.pop();
    		 while (topOperator != '(') {
    			 operandTwo = valStack.pop();
    			 operandOne = valStack.pop();
     
    			 if      (topOperator == '*')    result = operandOne * operandTwo;
    			 else if (topOperator == '+')    result = operandOne + operandTwo;
    			 else if (topOperator == '-')    result = operandOne - operandTwo;
    			 else
    			       throw new InfixException("Illegal symbol: " + topOperator);
     
    			 valStack.push(result);			 
    			 topOperator = opStack.pop();	 
    		 }
    		 break;
         default:
        	 break;	
    	    }	 
       }
    	 while(!opStack.isEmpty()){
    		 topOperator = opStack.pop();
    		 operandTwo = valStack.pop();
    		 operandOne = valStack.pop();
     
    		 if      (topOperator == '*')    result = operandOne * operandTwo;
    		 else if (topOperator == '+')    result = operandOne + operandTwo;
    		 else if (topOperator == '-')    result = operandOne - operandTwo;
    		 else
    		       throw new InfixException("Illegal symbol: " + topOperator);
     
    		 valStack.push(result);	
    	 }
     
    	double answer = valStack.peek();
    	return answer;
     
    	}
     
    	 public static int getPriority(char first) {
    			if      (first == '*' || first == '/')
    				return 1;
    			else if (first == '+' || first == '-')
    				return 2;
    			else if (first == '=')
    				return 3;
    			else
    				return Integer.MIN_VALUE;
    		}
     
    	 public static final Pattern CHARACTER =
    		     Pattern.compile("\\S.*?");  
         public static final Pattern UNSIGNED_DOUBLE =
    		     Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([Ee][-+]?\\d+)?.*?");
    }

    And here is the MAIN:

    MAIN:

    import java.util.Scanner;
     
    public class InfixConsole {
      public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
     
        String line = null;          // string to be evaluated
        double answer;               // result of evaluation
     
          // Get next expression to be processed.
          System.out.print("Enter an infix expression to be evaluated: ");
          line = console.nextLine();
     
            answer = InfixEvaluation.evalz(line);
     
            // Output result.
            System.out.println();
            System.out.println("Result = " + answer);
      	}
    }

    I also have a small error exception class.. if I need to put that too please let me know. Thanks!


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Using Stack Data Type to Solve an Infix Expression

    while(console.hasNext( )) {
     
    	}

    You have a mismatched bracket so your program gets stuck in an infinite loop.

  3. #3
    Junior Member
    Join Date
    Oct 2011
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Using Stack Data Type to Solve an Infix Expression

    Alright.. wow, I didn't even notice that. I fixed it now I am receiving this error:


    Exception in thread "main" java.util.EmptyStackException
    at java.util.Stack.peek(Stack.java:85)
    at java.util.Stack.pop(Stack.java:67)
    at InfixEvaluation.evalz(InfixEvaluation.java:85)
    at InfixConsole.main(InfixConsole.java:14)
    Last edited by patriots1049; October 8th, 2011 at 10:39 PM. Reason: Stupid Comment

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Using Stack Data Type to Solve an Infix Expression

    It's not mismatched persay, but it's in the wrong place.

    In your evalz method you have that piece of code that's intended to iterate through tokens of the expression, but instead of having the parsing code inside of it you have it after it. Simply move the closing brace to where it needs to be to include the parsing code in the while loop.

    Suggestion: If you're using an IDE, see if there's an "auto-format" code function (In know Eclipse has one, hotkey = CTRL+SHIFT+F). It's much easier to check for problems like this if your code is properly formatted (much easier to read, too).

  5. #5
    Junior Member
    Join Date
    Oct 2011
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Using Stack Data Type to Solve an Infix Expression

    I would love to format it that way but my teacher is very strict on using "his" guidelines. So the way I have it formatted is the way HE thinks is best. But I did fix that stupid error on my part and am receiving the error above ^^^ (I edited the post).

  6. #6
    Junior Member
    Join Date
    Oct 2011
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Using Stack Data Type to Solve an Infix Expression

    This is the psuedocode provided by the teacher as well.

    Algorithm evaluateInfix (infix)
        // Evaluates an infix expression.
        operatorStack = a new empty stack
        valueStack = a new empty stack
        while (infix has characters left to process)
    {
        nextCharacter = next nonblank character of infix
            switch (nextCharacter)
        {
            case variable:
                valueStack.push (value of the variable nextCharacter)
                    break
                    case '^':
                        operatorStack.push (nextCharacter)
                        break
                    case '+':
                    case '-':
                    case '*':
                    case '/':
                        while (!operatorStack.isEmpty () and
                            precedence of nextCharacter <= precedence of operatorStack.peek ())
                        {
                            // Execute operator at top of operatorStack
                            topOperator = operatorStack.pop ()
                            operandTwo = valueStack.pop ()
                            operandOne = valueStack.pop ()
                            result = the result of the operation in topOperator and its operands
                            operandOne and operandTwo
                            valueStack.push (result)
                        }
                        operatorStack.push (nextCharacter)
                        break
                    case '(':
                        operatorStack.push (nextCharacter)
                        break
                    case ')':  // stack is not empty if infix expression is valid
                        topOperator = operatorStack.pop ()
                        while (topOperator != '(')
                        {
                            operandTwo = valueStack.pop ()
                            operandOne = valueStack.pop ()
                            result = the result of the operation in topOperator and its operands
                            operandOne and operandTwo
                            valueStack.push (result)
                            topOperator = operatorStack.pop ()
                        }
                        break
                    default:
                        break
        }
    }
    while (!operatorStack.isEmpty ())
    {
        topOperator = operatorStack.pop ()
            operandTwo = valueStack.pop ()
            operandOne = valueStack.pop ()
            result = the result of the operation in topOperator and its operands
            operandOne and operandTwo
            valueStack.push (result)
    }
    return valueStack.peek ()

  7. #7
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Using Stack Data Type to Solve an Infix Expression

    In Eclipse you can define how the auto-formatter works (I don't use the standard format). I can see a few places in your code where your formatting is inconsistent (unless that's really what your teacher wants, which I doubt).

    It's possible that you can modify the auto-formatter to format as your teacher wants it to be formatted (maybe something to play around with on a lazy evening).

    What inputs are you using to get that error?

  8. #8
    Junior Member
    Join Date
    Oct 2011
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Using Stack Data Type to Solve an Infix Expression

    That's excellent information to know. Thanks! I'll definitely take a look at the formatter.

    But anyways, I'm just testing it out with a simple expression (8+8) ... and that doesn't work. It needs to handle all sort of infix (normal) expressions such as (5+5) + 6*3 + 11 ..

  9. #9
    Junior Member
    Join Date
    Oct 2011
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Using Stack Data Type to Solve an Infix Expression

    That's excellent information to know. Thanks! I'll definitely take a look at the formatter.

    But anyways, I'm just testing it out with a simple expression (8+8) ... and that doesn't work. It needs to handle all sort of infix (normal) expressions such as (5+5) + 6*3 + 11 ..

  10. #10
    Junior Member
    Join Date
    Oct 2011
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Using Stack Data Type to Solve an Infix Expression

    ***UPDATE***

    I got it to work.. but not fully. I can enter an expression like 5 + 5 and it will work. ( 5 + 5 )... will not work. And if I enter an expression without spaces it will not work.

    I get this error:


    Exception in thread "main" java.util.EmptyStackException
    at java.util.Stack.peek(Stack.java:85)
    at java.util.Stack.pop(Stack.java:67)
    at InfixEvaluation.evalz(InfixEvaluation.java:45)
    at InfixConsole.main(InfixConsole.java:14)

Similar Threads

  1. [SOLVED] what data type should i use in MySql for a java object to be saved
    By chronoz13 in forum JDBC & Databases
    Replies: 4
    Last Post: October 9th, 2011, 08:17 AM
  2. Primitive data type
    By stuart harper in forum What's Wrong With My Code?
    Replies: 4
    Last Post: September 17th, 2011, 01:14 PM
  3. About heap data type
    By PaddyWangTheGG in forum Algorithms & Recursion
    Replies: 2
    Last Post: May 17th, 2010, 04:02 PM
  4. Selection Sorting of Data type (Char)
    By chronoz13 in forum Algorithms & Recursion
    Replies: 1
    Last Post: December 20th, 2009, 08:28 PM
  5. Java error "java.lang.StackOverflowError"
    By sanatkumar in forum Exceptions
    Replies: 2
    Last Post: July 7th, 2009, 03:40 PM