What is a postfix expression?

An expression where in the operator is placed after the operands is called a postfix expression. For example an expression (also called infix expression) 2 + 3 in postfix is 2 3 +, expression 2 + 3 * 4 in postfix is 2 3 4 * +

In this article we will look at how to develop an postfix expression evaluator using BDD approach. Our evaluator would handle Addition, Subtraction, Multiplication and Division of floating and integer numbers.

BDD in action

Let us create a maven application for our BDD experiment. I am using Eclipse as my IDE. Once you have your project created, add the following dependencies in the pom.xml

<dependency>
  <groupId>info.cukes</groupId>
  <artifactId>cucumber-java</artifactId>
  <version>1.2.5</version>
  <scope>test</scope>
</dependency>
<!-- https://mvnrepository.com/artifact/info.cukes/cucumber-junit -->
<dependency>
  <groupId>info.cukes</groupId>
  <artifactId>cucumber-junit</artifactId>
  <version>1.2.5</version>
</dependency>

In BDD we first write acceptance tests. These acceptance tests are tests which would test the complete module/application there by declaring it to satisfy the user requirements. And these can be captured at the time of creating the acceptance criteria for a user story (concept widely used in scrum based agile software development methodology). These tests tend to be more user requirement focused and are often written in collaboration with the customer or customer representative or the product owner.

At the stakeholders end

As the people involved in the development of acceptance tests tend to non-technical, there is a Domain Specific Languge (DSL) available which helps in capturing the acceptance tests. This DSL is called Gherkin. And a tool called Cucumber helps in generating tests and then executing them. This generation and execution of tests is all behind the scenes and is carried out by the developer.

Let us see how a sample Gherkin file (ends with a .feature extension) looks like:

#comment
# there can be only 1 feature in a .feature file
Feature: Feature name
    feature description

# there can be multiple scenarios, which means multiple possibilities the feature can be used 
Scenario: Scenario 1
Given some input "abc"
And another input "xyz"
When user performs some action
Then the result should be "pqr"

# similarly we can have multiple scenarios

The above feature file is pretty clear and is mostly english language based. (This is the beauty of DSLs). There are few key words in the above file like Feature, Scenario, Given, And, When, Then and few more. And there are some restrictions like there can be only 1 Feature, And at the beginning of new line should be And and not and, then and can occur with in the sentence as normal and and so on. (I know too many ands). But such restrictions are what is imposed by the DSL.

Generating such feature files is quite simple and we can easily collaborate with stakeholders to capture their requirements and specifications by using examples and these examples can be written in form of Scenarios.

Developers End

The developer can take this feature file and generate java code. This java code is nothing but collection of methods backing each Given, When, Then clauses written in the feature file. There are different ways to generate it and I will show you one such way in this article.

Dive into code

Let us now dive into the code.

Create a feature file postfix-evaluator.feature in the location src/test/resources

Feature: Testing Post Fix evaluator
	We would use this to test our post fix evaluator
	
Scenario: Testing the evaluator with sum only
Given User enters "2 3 5 + +"
When User asks for result
Then result should be "10"

Scenario Outline: Testing the evaluator with complex expressions
Given User enters <expression>
When User asks for result
Then result should be <result>

Examples:
    | expression | result |
    | "3 4 5 + -" | "-6" |
    | "5 1 2 + 4 * + 3 -" | "14"  |
    | "5 2 3 ^ + 5 8 + " | "13"  |
    | "2 1 12 3 / - +" | "-1" |
    | "6 3 - 2 ^ 11 - " | "-2" | 

You know Scenario, but what is this Scenario Outline? It is a parameterized version of Scenario which means that the Given, When, Then specified for the Scenario Outline are executed for each of the test input provided in the Example section.

But how do we link the Examples and Given, When, Then?

The first row of the Example section indicate the name of the variables to which the value is assigned. And the same variable name can be used in the parameterized clauses of Given, When, Then. And you parameterize the clauses using .

Now to generate the Java code for this feature file, let us create a JUnit test runner TestPostFixEvaluator.java in src/test/java/bdd

package bdd;

import org.junit.runner.RunWith;

import cucumber.api.CucumberOptions;
import cucumber.api.junit.Cucumber;

@RunWith(Cucumber.class)
@CucumberOptions(features = "src/test/resources/")
public class TestPostFixEvaluator {

}

Run the above test and you will see a message like:

6 Scenarios ([33m6 undefined[0m)
18 Steps ([33m18 undefined[0m)
0m0.000s


You can implement missing steps with the snippets below:

@Given("^User enters \"([^\"]*)\"$")
public void user_enters(String arg1) throws Throwable {
    // Write code here that turns the phrase above into concrete actions
    throw new PendingException();
}

@When("^User asks for result$")
public void user_asks_for_result() throws Throwable {
    // Write code here that turns the phrase above into concrete actions
    throw new PendingException();
}

@Then("^result should be \"([^\"]*)\"$")
public void result_should_be(String arg1) throws Throwable {
    // Write code here that turns the phrase above into concrete actions
    throw new PendingException();
}

The above message contains the missing steps. So let us copy the above missing steps into class PostFixEvaluatorSteps in the package bdd under src/test/java and also add the code to test our post fix evaluator as shown below

package bdd;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import cucumber.api.java.en.Given;
import cucumber.api.java.en.Then;
import cucumber.api.java.en.When;
import evaluator.PostFixEvaluator;

public class PostFixEvaluatorSteps {
  PostFixEvaluator evaluator;
  Double computedResult;
  
  @Given("^User enters \"([^\"]*)\"$")
  public void user_enters(String expression) throws Throwable {
    evaluator = new PostFixEvaluator(expression);
  }

  @When("^User asks for result$")
  public void user_asks_for_result() throws Throwable {
    computedResult = evaluator.evaluate();
  }

  @Then("^result should be (\\d+)$")
  public void result_should_be(Double result) throws Throwable {
    assertEquals(result, computedResult);
  }
  
  @Then("^result should be \"([^\"]*)\"$")
  public void result_should_be(String result) throws Throwable {
    assertTrue(Double.parseDouble(result) == computedResult);
  }
 
}

Running the above will give up all sorts of abuses from the java compiler. So let us create a PostFixEvaluator class in the package evaluator under src/main/java with the class definition as shown below:

package evaluator;

import java.util.Stack;

public class PostFixEvaluator {
  
  public final String expression;
  
  public PostFixEvaluator(String expression) {
    this.expression = expression;
  }
    
  public Double evaluate(){ return 0d; }
}

And if you run the test TestPostFixEvaluator, you will see that all the tests as failing as shown below:

To implement a Post fix evaluator we make use of Stack. The way it works is:
1. If you encounter an operand, push it to stack
2. If you encounter a binary operator pop two elements and push the result to stack
3. If you encounter a unary operator pop 1 element and push the result to stack
4. If you have come to the end of expression then pop the stack to get the result.

There are various error conditions which we can handle:
1. If at the end of expression stack is empty, then we dont have any result
2. If at the end of expression stack has more than 1 element then we dont have enough operators, so expression is invalid
3. If on encountering an operator, we dont have enough operands in the stack, then the expression is invalid.
and so on.

We can update the PostFixEvaluator class with the code below (I havent considered error scenarios. We can easily add some negative tests and then write code to pass those negative tests, refactoring becomes easy as we already have tests for our feature).

package evaluator;

import java.util.Stack;

public class PostFixEvaluator {
  
  public final String expression;
  
  public PostFixEvaluator(String expression) {
    this.expression = expression;
  }
  
  Stack<Double> pfStack = new Stack<Double>();
  
  public Double evaluate(){
    String [] exprArray = expression.split("\\s+");
    for ( String elem : exprArray){
      if ( isOperator(elem)){
          Double operand2 = pfStack.pop();
          Double operand1 = pfStack.pop();
          switch (elem) {
          case "*":
            pfStack.push(operand1 * operand2);
            break;
          case "+":
            pfStack.push(operand1 + operand2);
            break;
          case "-":
            pfStack.push(operand1 - operand2);
            break;
          case "/":
            pfStack.push(operand1 / operand2);
            break;
          case "^":
            pfStack.push(Math.pow(operand1, operand2));
            break;
          default:
            throw new RuntimeException("Unsupported operator");
        }
      }else{
        pfStack.push(Double.parseDouble(elem));
      }
    }
    
    if ( pfStack.isEmpty()){
      throw new RuntimeException("Stack is empty, no result found");
    }
    return pfStack.pop();
  }
  
  private boolean isOperator(String element){
    switch (element) {
    case "+":
    case "-":
    case "/":
    case "*":
    case "^":
      return true;
    default:
      return false;
    }
  }
  
}

It is a pretty naive design, one can refactor and also refactor to use Strategy design pattern. This is all possible because we have acceptance tests, if we make some error during the refactoring, then the acceptance tests will flag them.

Let us run the test TestPostFixEvaluator now and see that all the scenarios are getting executed successfully:

This was a simple introduction to BDD. In the next article I will show how we can apply TDD exclusively and then an article with a mix of BDD and TDD.

The source for this is available on Github: https://github.com/sanaulla123/bdd-tdd-demo

Looking forward to hear your feedback!