• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
SteveDeFact0

prefix evaluation using stacks in java

2 posts in this topic

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?

0

Share this post


Link to post
Share on other sites

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);
	}
}
1

Share this post


Link to post
Share on other sites

 

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!

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0