Infix Expression Evaluator

post_fix_algorithm_thumbnail

Given an arithmetic expression in the infix notation, this algorithm computes its value in postfix notation and then computes an arithmetic expression. Using a GUI-based interface we can evaluates a C-style arithmetic expression and display its value.

For some background, the C language does not have separate Boolean data types and hence has NO Boolean expressions. It handles Boolean values true and false as non-zero and zero numbers. (Zero is false, and anything other than zero is true). An expression in C contains, numbers, arithmetic and comparison operators and logical connectives. We must first accommodate for this missing Boolean ability.

The algorithm is comprised of the following files:

  • ArrayListStack.java
  • ArrayStack.java
  • Expression.java
  • ExpressionEvaluator.java
  • ExpressionEvaluatorTester.java
  • ExpressionGUI.java
  • InfixToPostfixConverter.java
  • IStack.java
  • PostfixEvaluator.java
  • Token.java
    • For simplicity, we will only handle:

      • comparison operators: <, <=, >, >=, ==, !=
      • binary logical operators: &&, ||.
      • Binary arithmetic operators +, -, *, /, %

      We allow positive integer arguments and only those operators mentioned above. We assume C-style evaluation: false = 0 and true = 1 (anything non-zero). Thus 1 > 2 has a value of 0 (false).

      public class InfixToPostfixConverter
      {
          // Expression to be  converted
          private Expression infixExpression;
          
          //Largest size of the stack
          private final int MAXSTACKSIZE = 20;
          
          //Resulting postfix expression
          private Expression postfixExpression;
          
          /**
           * Constructor: Just assigns the parameter to instance variable
           */
          public InfixToPostfixConverter(Expression infix)
          {
              infixExpression = infix;
          }
          
          /**
           * Main conversion algorithm. 
           */
          public void convertToPostfix()
          {
              //Create an empty postfix expression
              postfixExpression = new Expression();
                  
              //create an empty operator stack
              ArrayStack<Token> operatorStack = new ArrayStack<Token>(MAXSTACKSIZE);
              
              //Temporary local variables
              Token nextToken = null;
              Token topOfStack = null;
              
              //Main loop
              ArrayList<Token> expr = infixExpression.getExpression();
              for (int k = 0; k < expr.size(); k++)
              {
                  //Get the next token from infix expression
                  nextToken = expr.get(k);
                  
                  //If it is an operand append it to postfix
                  if (nextToken.isOperand())
                      postfixExpression.add(nextToken);
                      
                  //If it is an open parenthesis push it into stack
                  else if (nextToken.isOpenParen())
                      operatorStack.push(nextToken);
                //If next token is a closed parenthesis
                  else if (nextToken.isClosedParen())
                  {
                      //Keep pulling operators out of stack and appending
                      //them to postfix, until top of stack is an open paren
                      topOfStack = operatorStack.top();
                      while (!topOfStack.isOpenParen())
                      {
                          postfixExpression.add(topOfStack);
                          operatorStack.pop();
                          topOfStack = operatorStack.top();
                      }
                      //and then discard the open paren
                      operatorStack.pop();
                  }
                  //If it is an operator ...
                  else if (nextToken.isOperator())
                  {
                      // get the precedence of this token
                      int tokenPrecedence = nextToken.getPrecedence();
                      
                      // If stack is empty, push nextToken into stack
                      if (operatorStack.isEmpty())
                         operatorStack.push(nextToken);
                      else 
                      {
                          //Get the precedence of the top of the stack
                          topOfStack = operatorStack.top();
                          
                          //If the top of stack is an open parenthesis push nextToken
                          if (topOfStack.isOpenParen())
                              operatorStack.push(nextToken);
                          else
                          {
                              //Get the precedence of the top of stack
                              int stackPrecedence = topOfStack.getPrecedence();
                              
                              //if nextToken's precedence is > that of top of stack's
                              //push next token into stack
                              if (tokenPrecedence > stackPrecedence)
                                  operatorStack.push(nextToken);
                              else
                              {
                                  //Keep pulling operators out of stack and appending
                                  //them to postfix, as long all all these conditions are true
                                  while ((tokenPrecedence <= stackPrecedence) &&
                                          (!topOfStack.isOpenParen()) &&
                                          (!operatorStack.isEmpty()))
                                  {
                                      topOfStack = operatorStack.pop();
                                      postfixExpression.add(topOfStack);
                                      if (!operatorStack.isEmpty())
                                      {
                                          topOfStack = operatorStack.top();
                                          stackPrecedence = topOfStack.getPrecedence();
                                      }
                                  }
                                  
                                  //At the end push nextToken into Stack
                                  operatorStack.push(nextToken);
                              }
                          }
                      }
                  }
                  
                  else
                  {
                      System.out.println
                          ("Illegal String in InfixToPostfixConverter");
                      break;
                  }
              }
              //At the end of the infix expression: pull all the operators 
              //out of the stack and append them to postfix
              while (!operatorStack.isEmpty())
              {
                  topOfStack = operatorStack.pop();
                  postfixExpression.add(topOfStack);
              }
          }
          /**
           * Retriever method: returns the current postfix expression
           */
          public Expression getPostfix()
          {
              return postfixExpression;
          }
         
      }

      To demonstrate the algorithm, we will use a tester and we will convert and evaluate the following infix expressions:

      Infix Expression:       10 * 5 + 3
      Postfix Expression:     10 5 * 3 +
      Value of Expression:    53
      
      Infix Expression:       10 * ( 7 + ( 12 - 9 ) ) / 10
      Postfix Expression:     10 7 12 9 - + * 10 /
      Value of Expression:    10
      
      Infix Expression:       100 % ( ( 3 + 2 ) + 3 ) / 4
      Postfix Expression:     100 3 2 + 3 + % 4 /
      Value of Expression:    1
      

      And to demonstrate the GUI, we can manually enter infix values and conclude their arithmetic result:

      GUI1

      Leave a Comment

      Your email address will not be published.