Sign in to follow this  
duHOSSval

Infix to postfix, and evaluate

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this