Skip to Main Content

Java Programming

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

How do you implement an algorithm?

807606Apr 4 2007 — edited Apr 4 2007
I need to implement the algorithm 'evaluatePostfix', as a static method of the class Postfix (code provided). How do I do this?

I am designing a program to evaluate a postfix expression using stacks.
public class Postfix 
{
  /** Task: Creates a postfix expression that represents a given infix 
   *        expression.
   *  @param infix  a string that is a valid infix expression
   *  @return a string that is the postfix expression equivalent to 
   *          infix */
  public static String convertToPostfix(String infix)
  {
    StringBuilder postfix = new StringBuilder();
    StackInterface<Character> operatorStack = new LinkedStack<Character>();
    int characterCount = infix.length();
    char topOperator;
    
    for (int index = 0; index < characterCount; index++)
    {
      boolean done = false;
      char nextCharacter = infix.charAt(index);
      
      if (isVariable(nextCharacter))
        postfix = postfix.append(nextCharacter);
      else
      {
        switch (nextCharacter)
        {
          case '^':
            operatorStack.push(nextCharacter);
            break;
            
          case '+': case '-': case '*': case '/':
            while (!done && !operatorStack.isEmpty())
            {
              topOperator = operatorStack.peek();
              
              if (getPrecedence(nextCharacter) <= getPrecedence(topOperator))
              {
                postfix = postfix.append(topOperator);
                operatorStack.pop();
              } 
              else
                done = true;
            } // end while
            
            operatorStack.push(nextCharacter);
            break;
            
          case '(':
            operatorStack.push(nextCharacter);
            break;
            
          case ')': // stack is not empty if infix expression is valid
            topOperator = operatorStack.pop();
            while (topOperator != '(')
            {
              postfix = postfix.append(topOperator);
              topOperator = operatorStack.pop();
            } // end while
            break;
            
          default: break;
        } // end switch
      } // end if
    } // end for
    
    while (!operatorStack.isEmpty())
    {
      topOperator = operatorStack.pop();
      postfix = postfix.append(topOperator);
    } // end while
    
    return postfix.toString();
  } // end convertToPostfix
  
  /** Task: Indicates the precedence of a given operator.
   *  @param operator  a character that is (, ), +, -, *, /, or ^
   *  @return an integer that indicates the precedence of operator: 
   *          0 if ( or ), 1 if + or -, 2 if * or /, 3 if ^, -1 if 
   *          anything else */
  private static int getPrecedence(char operator)
  {
    switch (operator)
    {
      case '(': case ')': return 0;
      case '+': case '-': return 1;
      case '*': case '/': return 2;
      case '^':           return 3;
    } // end switch
    
    return -1;
  } // end getPrecedence
  
  private static boolean isVariable(char character)
  {
    return Character.isLetter(character);
  } // end isVariable
} // end Postfix
Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on May 2 2007
Added on Apr 4 2007
15 comments
444 views