Jump to content
  • Advertisement
Sign in to follow this  
duHOSSval

Infix to postfix, and evaluate

This topic is 3713 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm writing a program to take an infix expression, covert it to postfix, and then evaluate it. I have a stack already created. I'll put my code below. I know I have the concept down, I'm just having trouble placing things where they need to be and such. Any help would be great.
import java.util.*;
import javax.swing.JOptionPane;

public class Eval
{
  
  public static void main( String args[] )
  {
    
    try
    {
      String expression = JOptionPane.showInputDialog( "Enter expression: " );
      JOptionPane.showMessageDialog( null, "Expression: " + expression );
      
      String postfix = toPostfix( expression );
      JOptionPane.showMessageDialog( null, "Postfix: " + postfix );
      
      Integer result = evaluate( postfix );
      JOptionPane.showMessageDialog( null, "Result: " + result.toString() );
    }
    catch( Exception e )
    {
      JOptionPane.showMessageDialog( null, "Error: " + e.getMessage() );
    }
  }

  // The evaluate method is called with the string representing the
  // infix expression.  The first thing it needs to do is call the
  // toPostfix method to create a postfix version of the expression. Then,
  // use the algorithm from the text to evaluate the postfix expression.
  public static Integer evaluate( String postfix ) throws Exception
  {
    //StringTokenizer st = new StringTokenizer(postfix);
    ObjStack1 s = new ObjStack1();
    Integer result;
    
    
    
    
    
    if(isOperator(postfix))
    {
      
      Integer x = (Integer) s.pop();
      Integer y = (Integer) s.pop();
      result = calculate(y,postfix,x);
      s.push(result);
    }
      
    else
    {
      s.pop();
    }
    return result;
    
   
    
    
   
    
    
    
     
    
  }
  
  // This function simply takes a string representing an infix expression 
  // and creates a new string that is the postfix representation.
  public static String toPostfix( String infix ) throws Exception
  {
    StringTokenizer st = new StringTokenizer(infix);
    ObjStack1 s = new ObjStack1();
    
    String output, postfix;
    
    while(st.hasMoreTokens())
    {
  
      while(!s.isEmpty())
      {
        postfix = st.nextToken();
        if(postfix.equals("("))
        {
          s.push(output);
        }
        else if (isOperator(postfix))
        {
          if(precedenceValue(postfix) <= precedenceValue())
          {
            s.pop();
            postfix = postfix + "" + s.pop();
          }
        }
        else if (postfix.equals(")"))
        {
          if(s.peek() != ("("))
          {
            s.pop();
            postfix = postfix + "" + s.pop();
          }
          postfix = postfix + "" + s.pop() + ("(");
        }
        else
        {
          postfix += postfix + "";
        }
      }
    }
    return postfix;
  }
    
  
  // This method takes two Integer objects and an operator (which is a string)
  // and returns a new Integer which is the result of applying the operation
  // to the two Integer parameters.
  public static Integer calculate( Integer n1, String op, Integer n2 )
  { if( op.equals( "+" ) )
    { return new Integer( n1.intValue() + n2.intValue() );
    }
    else if( op.equals( "-" ) )
    { return new Integer( n1.intValue() - n2.intValue() );
    }
    else if( op.equals( "*" ) )
    { return new Integer( n1.intValue() * n2.intValue() );
    }
    else if( op.equals( "&#47;" ) )
    { return new Integer( n1.intValue() / n2.intValue() );
    }
    else if( op.equals( "%" ) )
    { return new Integer( n1.intValue() % n2.intValue() );
    }
    else // op.equals( "^" )
    { return new Integer( ( int )Math.pow( n1.intValue(), n2.intValue() ) );
    }
  }

  // Takes a string as a parameter and determines if it is an operator.
  public static boolean isOperator( String s )
  { return ( s.equals( "^"  ) || s.equals( "%"  ) ||
             s.equals( "*"  ) || s.equals( "&#47;"  ) ||
             s.equals( "+"  ) || s.equals( "-"  ) );
  }

  // Determiens if the first operater has lower or equal precedence 
  // than the second operator.
  public static boolean precedence( String op1, String op2 )
  { return ( precedenceValue( op1 ) <= precedenceValue( op2 ) );
  }
  
  // Returns an appropriate integer value as the precedence of the operator.
  public static int precedenceValue( String op )
  { if( op.equals( "^" ) )
    { return 3;
    }
    else if( op.equals( "*" ) || op.equals( "&#47;" ) || op.equals( "%" ) )
    { return 2;
    } 
    else if( op.equals( "+" ) || op.equals( "-" ) )
    { return 1;
    } 
    else
    { return 0;
    }
  }
}


Share this post


Link to post
Share on other sites
Advertisement
You have a lot of subtle logical problems. Most notably, you aren't using 'output' at all in toPostfix(), and reuse 'postfix' in a way that can't possibly be right. Also, evaluate() is receiving the entire postfix String, and then tries to check if it consists of just an operator token. Also, it creates its own, empty ObjStack1 (BTW, don't use numbers to "version" your classes; use a real version control system), and then tries to pop() from that.

You aren't modelling enough things to make the task easy to understand. Make a class to represent a Token, and give it methods like .evaluate(Stack) (if it represents a number, push self onto the provided stack; otherwise, do the appropriate calculation), .toString() (i.e., override Object#toString) and so on. Then make a representation of an Expression (it should be some kind of sequence of Tokens), and give it a .evaluate() (which will iterate over the Tokens, using a local Stack to calculate the final value).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!