Generating all possible postfix expressions

The following Java program returns the list of all possible postfix expressions for a given list of operands and operators. The number of all postfix expressions grows exponentially with the number of operands and is around 5 billion for 10 operands and 4 operators (*,+,/,-). The precise number of all possible postfix expressions is C(n-1)*(noOfOperators^(n-1)) where n is the number of operands and C(n-1) is the n-1th Catalan number.

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PostfixExpressionGeneratorSansRecursion {
	private static final String [] OPERATORS = new String[] {"*", "+", "/", "-"};
	public static void main(String[] args) {
		List<String> x = new ArrayList<String>();
		for (String ex : generateAllPostfixExpressions(x)){
	 * Assumes input is a list of single digit positive numbers.
	 * @param operands
	 * @return list of all possible postfix expressions for the given list of operands
	private static List<String> generateAllPostfixExpressions(List<String> operands) {
		List<String> allPossiblePostFixExprs = new ArrayList<String>();
		Stack<String> stack = new Stack<String>();
		stack.push(""); //start with a empty partial expression
		int finalPFExprLength = 2*operands.size() - 1;
		int sizeOfOperands = operands.size();
		while (!stack.isEmpty()) {
			String partialExpr = stack.pop();
			int partialExprLength = partialExpr.length();
			if (partialExprLength == finalPFExprLength) {
			int noOfOprdsConsumed = 0;
			for (char c : partialExpr.toCharArray())
				noOfOprdsConsumed += Character.isDigit(c) ? 1 : 0;
			if (2*noOfOprdsConsumed - partialExprLength > 1)
				for (String op : OPERATORS)
					stack.push(partialExpr + op);
			if (noOfOprdsConsumed != sizeOfOperands)
				stack.push(partialExpr + operands.get(noOfOprdsConsumed));
	    return allPossiblePostFixExprs;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s