Java soluction using RPN and Shunting-yard algorithm


  • 0
    K

    This solution proceeds with the problem into 3 basic steps:

    1. Tokenize the input - split input into meaningful tokens to simplify the work for other phases (Tokenizer class). This is not the crucial part of the solution and is done mainly to eliminate dealing with raw input during calcuations.
    2. Convert expression to Reverse Polish Notation (RPN) using the 'shunting-yard' algorithm - see https://en.wikipedia.org/wiki/Shunting-yard_algorithm (PolishConverter class).
      Since all operations have the same priority, no additional checks during processing the operators are needed.
    3. Evaluate the expression in RPN to obtain the final result. Expression is evaluated using the rule: "If operand occurred, put it onto the operand stack, if operation occurred, then pop the needed quantity of operands and push the result of computation back onto the stack". (PolishSolver class)

    Example:

    • Input: " 1 + (2- 3) "

    • After splitting the input into tokens, the result will be:
      [INTEGER:1][OPERATION:+][LPAREN][INTEGER:2][OPERATION:-][INTEGER:3][RPAREN]

    • After conversion to RPN, we will obtain (token definitions are omited):
      "1 2 3 - +"
      State of the stack and input during evaluation is [], -> [1] -> [1, 2] -> [1, 2, 3] -> [1, -1] -> [0] (tokens are consumed one by one).
      Final result is 0 - top of the stack.

    This solution can be extended to handle priorities of the operators (try to add multiplication to your implementation if the problem was too easy for you).

    P. S. Solution may be too verbose for such a problem, as some additional plumbing was done to make the code more clear.

    import java.util.*;
    
    class Solution {
    	
    	public int calculate(String s) {
    		Iterable<Token> infixExpression = Tokenizer.tokenize(s);
    		Iterable<Token> polishExpression = PolishConverter.convert(infixExpression);
    		
    		return PolishSolver.calculate(polishExpression);
    	}
    }
    
    enum TokenTypes {
    	OPERATION, INTEGER, LPAREN, RPAREN;
    }
    
    class Token {
    
    	public static final Token LPAREN = new Token(TokenTypes.LPAREN, null);
    
    	public static final Token RPAREN = new Token(TokenTypes.RPAREN, null);
    
    	private final TokenTypes tokenType;
    
    	private final String value;
    
    	private Token(TokenTypes tokenType, String value) {
    		this.tokenType = tokenType;
    		this.value = value;
    	}
    
    	public static Token integer(String value) {
    		return new Token(TokenTypes.INTEGER, value);
    	}
    
    	public static Token operation(String value) {
    		return new Token(TokenTypes.OPERATION, value);
    	}
    
    	public static Token operation(char value) {
    		return operation(String.valueOf(value));
    	}
    
    	public TokenTypes getTokenType() {
    		return tokenType;
    	}
    
    	public String getValue() {
    		return value;
    	}
    
    	@Override
    	public String toString() {
    		return String.format("%s: %s", tokenType, value);
    	}
    }
    
    enum Operations {
    
    	PLUS("+") {
    		@Override
    		public int compute(int left, int right) {
    			return left + right;
    		}
    	},
    	MINUS("-") {
    		@Override
    		public int compute(int left, int right) {
    			return left - right;
    		}
    	};
    
    	private String value;
    
    	Operations(String value) {
    		this.value = value;
    	}
    
    	public abstract int compute(int left, int right);
    
    	public static Operations fromToken(Token t) {
    		for (Operations op : values()) {
    			if (op.value.equals(t.getValue())) {
    				return op;
    			}
    		}
    		throw new IllegalArgumentException(
    				String.format("Token '%s' is not operation", t));
    	}
    }
    
    class Tokenizer {
    
    	public static List<Token> tokenize(String s) {
    		List<Token> result = new ArrayList<>();
    
    		int len = s.length();
    		int next = 0;
    		for (int position = 0; position < len; position = next) {
    			char current = s.charAt(position);
    			switch (current) {
    			case ' ':
    				next++;
    				break;
    			case '(':
    				result.add(Token.LPAREN);
    				next++;
    				break;
    			case ')':
    				result.add(Token.RPAREN);
    				next++;
    				break;
    			case '+':
    			case '-':
    				result.add(Token.operation(current));
    				next++;
    				break;
    			default:
    				while (next < len && Character.isDigit(s.charAt(next))) {
    					next++;
    				}
    				if (next == position) {
    					throw new IllegalStateException(
    							"Unable to consume integer");
    				}
    				result.add(Token.integer(s.substring(position, next)));
    				break;
    			}
    		}
    		return result;
    	}
    }
    
    class PolishConverter {
    
    	public static List<Token> convert(Iterable<Token> infixTokens) {
    		List<Token> result = new ArrayList<>();
    		Deque<Token> operations = new ArrayDeque<>();
    
    		for (Token token : infixTokens) {
    			switch (token.getTokenType()) {
    			case LPAREN:
    				operations.push(token);
    				break;
    			case RPAREN:
    				while (!Token.LPAREN.equals(operations.peek())) {
    					result.add(operations.pop());
    				}
    				operations.pop();
    				break;
    			case OPERATION:
    				while (!operations.isEmpty()
    						&& !Token.LPAREN.equals(operations.peek())) {
    					result.add(operations.pop());
    				}
    				operations.push(token);
    				break;
    			case INTEGER:
    				result.add(token);
    				break;
    			}
    		}
    		while (!operations.isEmpty()) {
    			result.add(operations.pop());
    		}
    		return result;
    	}
    }
    
    class PolishSolver {
    
    	public static int calculate(Iterable<Token> polishExpression) {
    		Deque<Integer> operandStack = new ArrayDeque<>();
    		for (Token token : polishExpression) {
    			TokenTypes type = token.getTokenType();
    			switch (type) {
    			case OPERATION:
    				int right = operandStack.pop();
    				int left = operandStack.pop();
    				int result = Operations.fromToken(token).compute(left, right);
    				operandStack.push(result);
    				break;
    			case INTEGER:
    				operandStack.push(Integer.valueOf(token.getValue()));
    				break;
    			default:
    				throw new IllegalArgumentException(
    						"Illegal token for polish notation");
    			}
    		}
    		return operandStack.pop();
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.