Jump to content

  • Log In with Google      Sign In   
  • Create Account

prefix evaluation using stacks in java


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 SteveDeFact0   Members   -  Reputation: 151

Like
0Likes
Like

Posted 06 April 2014 - 10:56 PM

I have to prefix evaluate a string like this

* + 12 8 + 3 7

 

I have to use two stacks to accomplish this. One stack holds values of sub-expressions as they are compiled, and the other stack to store operators that have not yet been applied. It would seem to me that it would be far more logical to do this from reverse but the project clearly does not allow this. So I've been working on this for a few hours and I am stumped. Any ideas?



Sponsor:

#2 dr01d3k4   Members   -  Reputation: 418

Like
1Likes
Like

Posted 07 April 2014 - 02:55 AM

I'm not entirely sure what you mean by "sub-expressions as they are compiled". Are you trying to rewrite the expression in infix/postfix notation or trying to evaluate an answer?

 

Also is this a homework question? They aren't allowed here and with the way you've worded it I'm not sure if this is an assignment or not.

 

After playing around for a bit, I got this which does both of those (though it's a bit ugly as it uses member variables to get around Java only allowing 1 return value). It's also not commented, but it should hopefully be clear what's going on:

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



public final class PrefixEvaluation {
	private final List<Token> tokens;
	private String infixExpression;
	private String postfixExpression;
	
	
	
	public PrefixEvaluation() {
		tokens = new ArrayList<Token>();
		infixExpression = "";
		postfixExpression = "";
	}
	
	
	
	public void addToken(final Token token) {
		token.index = tokens.size();
		tokens.add(token);
	}
	
	
	
	public String prefixExpressionToString() {
		final StringBuilder stringBuilder = new StringBuilder();
		
		for (final Token token : tokens) {
			stringBuilder.append(token.value);
			stringBuilder.append(" ");
		}
		
		String expression = stringBuilder.toString();
		expression = expression.trim();
		return expression;
	}
	
	
	
	public double evaluate() throws Exception {
		final Stack<Token> operators = new Stack<Token>();
		final Stack<Token> numbers = new Stack<Token>();
		final Stack<String> infixExpressions = new Stack<String>();
		final Stack<String> postfixExpressions = new Stack<String>();
		
		try {
			while (tokens.size() > 0) {
				final Token currentToken = tokens.remove(0);
				
				if (currentToken.type == TokenType.NUMBER) {
					numbers.push(currentToken);
				} else if (currentToken.type == TokenType.OPERATOR) {
					operators.push(currentToken);
				}
				
				infixExpressions.push(currentToken.value);
				postfixExpressions.push(currentToken.value);
				
				while (operators.size() > 0) {
					final Token topOperator = operators.peek();
					final int operatorIndex = topOperator.index;
					
					final int operandCount = getOperandCountForOperator(topOperator.value);
					
					if (numbers.size() >= operandCount) {
						
						Token number2 = numbers.peek();
						if (number2.index > operatorIndex) {
							number2 = numbers.pop();
						} else {
							break;
						}
						
						Token number1 = numbers.peek();
						if (number1.index > operatorIndex) {
							number1 = numbers.pop();
						} else {
							numbers.push(number2);
							break;
						}
						
						final Token operator = operators.pop();
						
						String number1Expression = infixExpressions.pop();
						String number2Expression = infixExpressions.pop();
						String operatorExpression = infixExpressions.pop();
						infixExpressions.push("(" + number2Expression + " " + operatorExpression + " "
							+ number1Expression + ")");
						
						number1Expression = postfixExpressions.pop();
						number2Expression = postfixExpressions.pop();
						operatorExpression = postfixExpressions.pop();
						postfixExpressions.push(number2Expression + " " + number1Expression + " "
							+ operatorExpression);
						
						final double result = evaluateResult(number1.value, operator.value, number2.value);
						final Token resultToken = new Token(Double.toString(result), TokenType.NUMBER,
							number2.index);
						numbers.push(resultToken);
						
					} else {
						break;
					}
				}
			}
			
		} catch (final IllegalArgumentException e) {
			e.printStackTrace();
		}
		
		double answer = 0;
		
		if (numbers.size() == 1) {
			answer = Double.parseDouble(numbers.pop().value);
		} else {
			throw new Exception("Error in parsing");
		}
		
		infixExpression = infixExpressions.pop();
		postfixExpression = postfixExpressions.pop();
		
		return answer;
	}
	
	
	
	private double evaluateResult(final String number1String, final String operator, final String number2String) {
		double result = 0;
		
		final double number1 = Double.parseDouble(number1String);
		final double number2 = Double.parseDouble(number2String);
		
		if (operator.equals("+")) {
			result = number1 + number2;
		} else if (operator.equals("-")) {
			result = number1 - number2;
		} else if (operator.equals("*")) {
			result = number1 * number2;
		} else if (operator.equals("/")) {
			result = number1 / number2;
		} else {
			throw new IllegalArgumentException("Operator unknown");
		}
		
		return result;
	}
	
	
	
	private int getOperandCountForOperator(final String operator) {
		int operandCount = 0;
		
		if (operator.equals("+") || operator.equals("-") || operator.equals("*") || operator.equals("/")) {
			operandCount = 2;
		} else {
			throw new IllegalArgumentException("Operator unknown");
		}
		
		return operandCount;
	}
	
	
	
	private static final class Token {
		public final String value;
		public final TokenType type;
		public int index;
		
		
		
		public Token(final String value, final TokenType type) {
			this(value, type, -1);
		}
		
		
		
		public Token(final String value, final TokenType type, final int index) {
			this.value = value;
			this.type = type;
			this.index = index;
		}
		
		
		
		@Override
		public String toString() {
			return value + " (" + type.toString() + ", " + index + ")";
		}
	}
	
	
	
	private enum TokenType {
		OPERATOR, NUMBER
	}
	
	
	
	public static void main(final String[] args) throws Exception {
		final PrefixEvaluation prefixEvaluation = new PrefixEvaluation();
		prefixEvaluation.addToken(new Token("*", TokenType.OPERATOR));
		prefixEvaluation.addToken(new Token("+", TokenType.OPERATOR));
		prefixEvaluation.addToken(new Token("12", TokenType.NUMBER));
		prefixEvaluation.addToken(new Token("8", TokenType.NUMBER));
		prefixEvaluation.addToken(new Token("+", TokenType.OPERATOR));
		prefixEvaluation.addToken(new Token("3", TokenType.NUMBER));
		prefixEvaluation.addToken(new Token("7", TokenType.NUMBER));
		
		final String prefixExression = prefixEvaluation.prefixExpressionToString();
		
		final double answer = prefixEvaluation.evaluate();
		
		final String infixExpression = prefixEvaluation.infixExpression;
		final String postfixExpression = prefixEvaluation.postfixExpression;
		
		System.out.println(prefixExression + " = " + infixExpression + " = " + postfixExpression + " = " + answer);
	}
}

Falling block colour flood game thing I'm making: http://jsfiddle/dr01d3k4/JHnCV/


#3 SteveDeFact0   Members   -  Reputation: 151

Like
0Likes
Like

Posted 07 April 2014 - 03:30 AM

 

I'm not entirely sure what you mean by "sub-expressions as they are compiled". Are you trying to rewrite the expression in infix/postfix notation or trying to evaluate an answer?

 

Also is this a homework question? They aren't allowed here and with the way you've worded it I'm not sure if this is an assignment or not.

 

After playing around for a bit, I got this which does both of those (though it's a bit ugly as it uses member variables to get around Java only allowing 1 return value). It's also not commented, but it should hopefully be clear what's going on:

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



public final class PrefixEvaluation {
	private final List<Token> tokens;
	private String infixExpression;
	private String postfixExpression;
	
	
	
	public PrefixEvaluation() {
		tokens = new ArrayList<Token>();
		infixExpression = "";
		postfixExpression = "";
	}
	
	
	
	public void addToken(final Token token) {
		token.index = tokens.size();
		tokens.add(token);
	}
	
	
	
	public String prefixExpressionToString() {
		final StringBuilder stringBuilder = new StringBuilder();
		
		for (final Token token : tokens) {
			stringBuilder.append(token.value);
			stringBuilder.append(" ");
		}
		
		String expression = stringBuilder.toString();
		expression = expression.trim();
		return expression;
	}
	
	
	
	public double evaluate() throws Exception {
		final Stack<Token> operators = new Stack<Token>();
		final Stack<Token> numbers = new Stack<Token>();
		final Stack<String> infixExpressions = new Stack<String>();
		final Stack<String> postfixExpressions = new Stack<String>();
		
		try {
			while (tokens.size() > 0) {
				final Token currentToken = tokens.remove(0);
				
				if (currentToken.type == TokenType.NUMBER) {
					numbers.push(currentToken);
				} else if (currentToken.type == TokenType.OPERATOR) {
					operators.push(currentToken);
				}
				
				infixExpressions.push(currentToken.value);
				postfixExpressions.push(currentToken.value);
				
				while (operators.size() > 0) {
					final Token topOperator = operators.peek();
					final int operatorIndex = topOperator.index;
					
					final int operandCount = getOperandCountForOperator(topOperator.value);
					
					if (numbers.size() >= operandCount) {
						
						Token number2 = numbers.peek();
						if (number2.index > operatorIndex) {
							number2 = numbers.pop();
						} else {
							break;
						}
						
						Token number1 = numbers.peek();
						if (number1.index > operatorIndex) {
							number1 = numbers.pop();
						} else {
							numbers.push(number2);
							break;
						}
						
						final Token operator = operators.pop();
						
						String number1Expression = infixExpressions.pop();
						String number2Expression = infixExpressions.pop();
						String operatorExpression = infixExpressions.pop();
						infixExpressions.push("(" + number2Expression + " " + operatorExpression + " "
							+ number1Expression + ")");
						
						number1Expression = postfixExpressions.pop();
						number2Expression = postfixExpressions.pop();
						operatorExpression = postfixExpressions.pop();
						postfixExpressions.push(number2Expression + " " + number1Expression + " "
							+ operatorExpression);
						
						final double result = evaluateResult(number1.value, operator.value, number2.value);
						final Token resultToken = new Token(Double.toString(result), TokenType.NUMBER,
							number2.index);
						numbers.push(resultToken);
						
					} else {
						break;
					}
				}
			}
			
		} catch (final IllegalArgumentException e) {
			e.printStackTrace();
		}
		
		double answer = 0;
		
		if (numbers.size() == 1) {
			answer = Double.parseDouble(numbers.pop().value);
		} else {
			throw new Exception("Error in parsing");
		}
		
		infixExpression = infixExpressions.pop();
		postfixExpression = postfixExpressions.pop();
		
		return answer;
	}
	
	
	
	private double evaluateResult(final String number1String, final String operator, final String number2String) {
		double result = 0;
		
		final double number1 = Double.parseDouble(number1String);
		final double number2 = Double.parseDouble(number2String);
		
		if (operator.equals("+")) {
			result = number1 + number2;
		} else if (operator.equals("-")) {
			result = number1 - number2;
		} else if (operator.equals("*")) {
			result = number1 * number2;
		} else if (operator.equals("/")) {
			result = number1 / number2;
		} else {
			throw new IllegalArgumentException("Operator unknown");
		}
		
		return result;
	}
	
	
	
	private int getOperandCountForOperator(final String operator) {
		int operandCount = 0;
		
		if (operator.equals("+") || operator.equals("-") || operator.equals("*") || operator.equals("/")) {
			operandCount = 2;
		} else {
			throw new IllegalArgumentException("Operator unknown");
		}
		
		return operandCount;
	}
	
	
	
	private static final class Token {
		public final String value;
		public final TokenType type;
		public int index;
		
		
		
		public Token(final String value, final TokenType type) {
			this(value, type, -1);
		}
		
		
		
		public Token(final String value, final TokenType type, final int index) {
			this.value = value;
			this.type = type;
			this.index = index;
		}
		
		
		
		@Override
		public String toString() {
			return value + " (" + type.toString() + ", " + index + ")";
		}
	}
	
	
	
	private enum TokenType {
		OPERATOR, NUMBER
	}
	
	
	
	public static void main(final String[] args) throws Exception {
		final PrefixEvaluation prefixEvaluation = new PrefixEvaluation();
		prefixEvaluation.addToken(new Token("*", TokenType.OPERATOR));
		prefixEvaluation.addToken(new Token("+", TokenType.OPERATOR));
		prefixEvaluation.addToken(new Token("12", TokenType.NUMBER));
		prefixEvaluation.addToken(new Token("8", TokenType.NUMBER));
		prefixEvaluation.addToken(new Token("+", TokenType.OPERATOR));
		prefixEvaluation.addToken(new Token("3", TokenType.NUMBER));
		prefixEvaluation.addToken(new Token("7", TokenType.NUMBER));
		
		final String prefixExression = prefixEvaluation.prefixExpressionToString();
		
		final double answer = prefixEvaluation.evaluate();
		
		final String infixExpression = prefixEvaluation.infixExpression;
		final String postfixExpression = prefixEvaluation.postfixExpression;
		
		System.out.println(prefixExression + " = " + infixExpression + " = " + postfixExpression + " = " + answer);
	}
}

Welp you just blew my mind man. You are one hell of a java programmer!






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS