/** * Recursive descent parsing lololo * ElpCalculator supports '+', '-', '/', '*', '^', '%', '√' operators so far * Order of operations is maintained and brackets are supported * Write expresions in a single line with any number of spaces and brackets * Example: ((((1+1)-(2+2))*2)-1+2^2) or 2 + ((-(-(-2)))) * * Throws exception when input is empty input has illegal char */ import java.util.*; import java.util.stream.Collectors; public class ElpCalculator { private static final TokenParser tokenParser = new TokenParser(); private static final Lexer lexer = new Lexer(); public static void main(String[] args) { try (Scanner scanner = new Scanner(System.in)) { final String nextLine = scanner.nextLine(); final List tokens = lexer.lex(nextLine.trim()); tokenParser.setTokens(tokens); final Operation operation = tokenParser.parseAndReset(); final StringBuilder visitor = new StringBuilder(); operation.accept(visitor); double res = operation.evaluate(); visitor.append(" = "); if (res == (int) res) { visitor.append((int) res); } else { visitor.append(res); } System.out.print(visitor); } } public static void throwUnexpected(List allTokens, List unexpectedTokens) { StringBuilder sb = new StringBuilder(); for (Token token : allTokens) { if (unexpectedTokens.contains(token)) { sb.append("[").append(token).append("]"); } else { sb.append(token); } } throw new IllegalArgumentException("unexpected token: " + sb); } } class Lexer { public List lex(String string) { if(string.isEmpty()){ throw new IllegalArgumentException("empty string"); } final List allTokens = new ArrayList<>(); final List lexResult = new ArrayList<>(); final List undefinedTokens = new ArrayList<>(); for (int i = 0; i < string.length(); i++) { char c = string.charAt(i); String cStr = String.valueOf(c); switch (c) { case ' ': break; case '(': collectToken(allTokens, lexResult, Token.Type.LPAREN, cStr); break; case ')': collectToken(allTokens, lexResult, Token.Type.RPAREN, cStr); break; case '+': collectToken(allTokens, lexResult, Token.Type.PLUS, cStr); break; case '-': collectToken(allTokens, lexResult, Token.Type.MINUS, cStr); break; case '*': collectToken(allTokens, lexResult, Token.Type.MULTIPLY, cStr); break; case '/': collectToken(allTokens, lexResult, Token.Type.DIVIDE, cStr); break; case '^': collectToken(allTokens, lexResult, Token.Type.POWER, cStr); break; case '%': collectToken(allTokens, lexResult, Token.Type.MODULO, cStr); break; case '√': collectToken(allTokens, lexResult, Token.Type.SQRT, cStr); break; case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': case '0': StringBuilder sb = new StringBuilder(); sb.append(c); for (int j = i + 1; j < string.length(); j++) { c = string.charAt(j); if (Character.isDigit(c) || c == '.' || c == 'E') { i++; sb.append(c); } else { break; } } final String toString = sb.toString(); if (!toString.matches("([0-9]+\\.[0-9E]+)|([0-9]+)")) { throw new IllegalArgumentException("invalid " + "number format: '" + toString + "'"); } collectToken(allTokens, lexResult, Token.Type.NUMBER, toString); break; default: collectToken(allTokens, undefinedTokens, Token.Type.UNDEFINED, cStr); break; } } if (!undefinedTokens.isEmpty()) { ElpCalculator.throwUnexpected(allTokens, undefinedTokens); } return lexResult; } private void collectToken(List allTokens, List specificTokenBucket, Token.Type type, String value) { Token t = new Token(type, value); specificTokenBucket.add(t); allTokens.add(t); } } class TokenParser { private int index = -1; private Token current; private List tokens; private boolean finished = false; public TokenParser() { } public Operation parseAndReset() { BinaryOperation result = expression(); List notParsed = tokens.stream() .filter(token -> !token.isParsed()) .collect(Collectors.toList()); if (!notParsed.isEmpty()) { ElpCalculator.throwUnexpected(tokens, notParsed); } index = -1; finished = false; return result; } public void setTokens(List tokens) { this.tokens = tokens; next(); } private void next() { if (index + 1 < tokens.size()) { index++; current = tokens.get(index); } else { finished = true; current = null; } } private boolean nextTokenType(Token.Type type) { if (finished) { return false; } while (current == null) { next(); } if (current.getType() == type) { current.parse(); next(); return true; } return false; } private BinaryOperation expression() { BinaryOperation left = term(); boolean plusOrMinus = true; while (plusOrMinus) { if (nextTokenType(Token.Type.PLUS)) { final AddOperation addOperation = new AddOperation(); addOperation.setLeft(left); addOperation.setRight(term()); left = addOperation; } else if (nextTokenType(Token.Type.MINUS)) { final SubtractOperation subtractOperation = new SubtractOperation(); subtractOperation.setLeft(left); subtractOperation.setRight(term()); left = subtractOperation; } else { plusOrMinus = false; } } return left; } private BinaryOperation term() { BinaryOperation left = factor(); boolean multiplyOrDivide = true; while (multiplyOrDivide) { if (nextTokenType(Token.Type.DIVIDE)) { final DivideOperation divideOperation = new DivideOperation(); divideOperation.setLeft(left); divideOperation.setRight(factor()); left = divideOperation; } else if (nextTokenType(Token.Type.MULTIPLY)) { final MultiplyOperation multiplyOperation = new MultiplyOperation(); multiplyOperation.setLeft(left); multiplyOperation.setRight(factor()); left = multiplyOperation; } else { multiplyOrDivide = false; } } return left; } private BinaryOperation factor() { final Token currentLocal = current; BinaryOperation res = null; if (nextTokenType(Token.Type.PLUS)) { res = new AddOperation(); BinaryOperation left = factor(); res.setLeft(left); return res; } else if (nextTokenType(Token.Type.MINUS)) { res = new SubtractOperation(); res.setLeft(factor()); return res; } else if (nextTokenType(Token.Type.LPAREN)) { res = new ParenthesisExpression(expression()); if (!nextTokenType(Token.Type.RPAREN)) { ElpCalculator.throwUnexpected(tokens, Collections.singletonList(currentLocal)); } } else if (nextTokenType(Token.Type.SQRT)) { final RootOperation rootOperation = new RootOperation(); rootOperation.setLeft(factor()); res = rootOperation; } else if (currentLocal != null && currentLocal.getType() == Token.Type.NUMBER) { currentLocal.parse(); res = new Number(currentLocal.getValue()); next(); } else { ElpCalculator.throwUnexpected(tokens, Collections.singletonList(tokens.get(index))); } if (nextTokenType(Token.Type.POWER)) { PowerOperation resP = new PowerOperation(); resP.setLeft(res); resP.setRight(factor()); res = resP; } if (nextTokenType(Token.Type.MODULO)) { final ModuloOperation moduloOperation = new ModuloOperation(); moduloOperation.setLeft(res); moduloOperation.setRight(factor()); res = moduloOperation; } return res; } } interface Operation { double evaluate(); void accept(StringBuilder visitor); } abstract class BinaryOperation implements Operation { protected BinaryOperation left, right; public void setLeft(BinaryOperation left) { this.left = left; } public void setRight(BinaryOperation right) { this.right = right; } protected boolean isUnary() { return right == null; } } class AddOperation extends BinaryOperation { @Override public double evaluate() { if (isUnary()) { return left.evaluate(); } return left.evaluate() + right.evaluate(); } @Override public void accept(StringBuilder visitor) { if (isUnary()) { left.accept(visitor); } else { left.accept(visitor); visitor.append("+"); right.accept(visitor); } } } class SubtractOperation extends BinaryOperation { @Override public double evaluate() { if (isUnary()) { return left.evaluate() * -1; } return left.evaluate() - right.evaluate(); } @Override public void accept(StringBuilder visitor) { if (isUnary()) { visitor.append("(").append("-"); left.accept(visitor); visitor.append(")"); } else { left.accept(visitor); visitor.append("-"); right.accept(visitor); } } } class Number extends BinaryOperation { private final double value; public Number(String value) { this.value = Double.parseDouble(value); } @Override public double evaluate() { return value; } @Override public void accept(StringBuilder visitor) { if ((int) value == value) { visitor.append((int) value); } else { visitor.append(value); } } } class RootOperation extends BinaryOperation { @Override public double evaluate() { return Math.sqrt(left.evaluate()); } @Override public void accept(StringBuilder visitor) { visitor.append("√"); left.accept(visitor); } } class ParenthesisExpression extends BinaryOperation { private final BinaryOperation expression; public ParenthesisExpression(BinaryOperation expression) { this.expression = expression; } @Override public double evaluate() { return expression.evaluate(); } @Override public void accept(StringBuilder visitor) { if (expression instanceof SubtractOperation && expression.isUnary()) { expression.accept(visitor); } else { visitor.append("("); expression.accept(visitor); visitor.append(")"); } } } class MultiplyOperation extends BinaryOperation { @Override public double evaluate() { return left.evaluate() * right.evaluate(); } @Override public void accept(StringBuilder visitor) { if (isUnary()) { left.accept(visitor); } else { left.accept(visitor); visitor.append("*"); right.accept(visitor); } } } class ModuloOperation extends BinaryOperation { @Override public double evaluate() { return left.evaluate() % right.evaluate(); } @Override public void accept(StringBuilder visitor) { if (isUnary()) { left.accept(visitor); } else { left.accept(visitor); visitor.append("%"); right.accept(visitor); } } } class DivideOperation extends BinaryOperation { @Override public double evaluate() { return left.evaluate() / right.evaluate(); } @Override public void accept(StringBuilder visitor) { if (isUnary()) { left.accept(visitor); } else { left.accept(visitor); visitor.append("/"); right.accept(visitor); } } } class PowerOperation extends BinaryOperation { @Override public double evaluate() { return Math.pow(left.evaluate(), right.evaluate()); } @Override public void accept(StringBuilder visitor) { if (isUnary()) { left.accept(visitor); } else { left.accept(visitor); visitor.append("^"); right.accept(visitor); } } } class Token { enum Type { LPAREN, RPAREN, MINUS, PLUS, MODULO, SQRT, MULTIPLY, DIVIDE, NUMBER, POWER, UNDEFINED } private final Type type; private final String value; private boolean isParsed; public Token(Type type, String value) { this.type = type; this.value = value; } public Type getType() { return type; } public boolean isParsed() { return isParsed; } public void parse() { isParsed = true; } public String getValue() { return value; } @Override public String toString() { return value; } }

Recursive Descent Calculator