import java.util.LinkedList;
import java.util.List;
import java.util.Optional;

public class Parser {

    private abstract class Expression {

    }

    private class BinaryOperation extends Expression {
        Expression leftExpression;
        String operator;
        Expression rightExpression;
        public BinaryOperation(Expression leftExpression, String operator, Expression rightExpression) {
            this.leftExpression = leftExpression;
            this.operator = operator;
            this.rightExpression = rightExpression;
        }
    }

    private class Variable extends Expression {
        String variableName;
        public Variable(String i) {
            this.variableName = i;
        }
    }

    private abstract class Value extends Expression {

    }

    private class Number extends Value {
        public String digits;
        public Number(String i) {
            this.digits = i;
        }
    }

    private class Decimal extends Value {
        public Number beforeDot;
        public Number afterDot;

        public Decimal(Number i1, Number i2) {
            this.beforeDot = i1;
            this.afterDot = i2;
        }
    }

    //starting method of the parser
    //parses a list of tokens
    public Expression parse(List<Lexer.Token> list) throws ParserException {
        if(list.isEmpty()) {
            throw new ParserException("empty token list");
        }

        List<Lexer.Token> ts = new LinkedList<>(list);
        Expression ast = parseExpression(ts);

        if(!ts.isEmpty()) {
            throw new ParserException("RuntimeError: " + ts.size() + " token(s) left");
        }
        return ast;
    }

    //called by method parse(...)
    //parses a list of tokens into an expression
    private Expression parseExpression(List<Lexer.Token> ts) throws ParserException {
        if(ts.isEmpty()) {
            throw new ParserException("SyntaxError: empty token list");
        }
        Expression ast;
        ast = parseBinaryOperation(ts);
        if(ast==null) {
            ast = parseVariable(ts);
            if(ast==null) {
                ast = parseValue(ts);
            }
            if(ast==null) {
                throw new ParserException("SyntaxError: invalid character");
            }
        }
        return ast;
    }

    //checks if a String only contains an allowed operator with parseCharacter(...)
    private Boolean parseOperator(String operator) throws ParserException {
        if(operator.length()>1) {
            throw new ParserException("SyntaxError: invalid length for an operator: " + operator);
        }
        if(!parseCharacter(operator, "+-*/^")) {
            throw new ParserException("SyntaxError: invalid operator character: " + operator);
        }
        return true;
    }

    private BinaryOperation parseBinaryOperation(List<Lexer.Token> ts) throws ParserException {
        if(ts.isEmpty()) {
            throw new ParserException("SyntaxError: empty token list");
        }
        if(ts.size()==1) {
            return null;
        }
        int index;
        for(index=0; index<ts.size(); index++) {
            if(ts.get(index).getType()== Lexer.TokenType.SPECIAL) {
                if(!parseCharacter(ts.get(index).getData(), ".")) {
                    break;
                }
            }
        }
        if(index==ts.size()) {
            return null;
        }
        //0
        //1
        //2
        //3
        //4 * => index=4

        //5
        //6
        //7
        List<Lexer.Token> leftList = new LinkedList<>();
        for(int i=0; i<index; i++) {
            leftList.add(ts.remove(0));
        }
        Expression leftExpression = parseExpression(leftList);
        String operator = ts.remove(0).getData();
        parseOperator(operator);
        Expression rightExpression = parseExpression(ts);

        /*
        if(parseCharacter(ts.get(1).getData(), ".")) {
            return null;
        }
        BinaryOperation operation;
        if(ts.get(1).getType()!= Lexer.TokenType.SPECIAL) {
            throw new ParserException("SyntaxError: unexpected operator: " + ts.get(1).getData());
        }
        List<Lexer.Token> leftList = new LinkedList<>();
        leftList.add(ts.remove(0));
        Expression leftExpression = parseExpression(leftList);
        String operator = ts.remove(0).getData();
        parseOperator(operator);
        Expression rightExpression = parseExpression(ts);

         */
        return new BinaryOperation(leftExpression, operator, rightExpression);
    }

    private Variable parseVariable(List<Lexer.Token> ts) throws ParserException {
        if (ts.isEmpty()) {
            throw new ParserException("SyntaxError: empty token list");
        }
        if (ts.get(0).getType() != Lexer.TokenType.VARIABLE) {
            return null;
        }

        String data = ts.remove(0).getData();
        if (data.isEmpty()) {
            throw new ParserException("SyntaxError: empty token");
        }

        if(!parseCharacter(data,"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")) {
            throw new ParserException("Invalid variable character: " + data);
        }
        return new Variable(data);
    }

    //called by method parseException(...)
    //parses a token/list of tokens into a value
    private Value parseValue(List<Lexer.Token> ts) throws ParserException {
        if (ts.isEmpty()) {
            throw new ParserException("SyntaxError: empty token list");
        }
        if (ts.get(0).getType() != Lexer.TokenType.NUMBER) {
            return null;
        }
        String data = ts.get(0).getData();
        if (data.isEmpty()) {
            throw new ParserException("SyntaxError: empty token");
        }

        Value value = null;
        if (ts.size()>1) {
            //if the next token is of TokenType.SPECIAL, check if it's a comma
            //if it is, create a decimal
            if(ts.get(1).getType() == Lexer.TokenType.SPECIAL) {
                if(parseComma(ts)) {
                    value = parseDecimal(ts);
                }
            }
        }
        if(value==null) {
            value = parseNumber(ts.remove(0).getData());
        }
        return value;
    }

    //called by method parseValue(...)
    //parses a decimal of a list of tokens & a string
    private Decimal parseDecimal(List<Lexer.Token> ts) throws ParserException {
        String data = ts.remove(0).getData();
        if(data.isEmpty()) {
            throw new ParserException("SyntaxError: empty data");
        }
        if(ts.size()==0) {
            throw new ParserException("SyntaxError: no tokens left to create Decimal");
        }
        Number beforeDot = (Number) parseNumber(data);
        ts.remove(0);
        data = ts.remove(0).getData();
        Number afterDot = (Number) parseNumber(data);
        return new Decimal(beforeDot, afterDot);
    }

    //called by method parseValue(...)
    //parses a String into a number
    private Number parseNumber(String data) throws ParserException{
        if (data.isEmpty()) {
            throw new ParserException("RuntimeException: empty token");
        }

        if (data.startsWith("0") && data.length() == 1) {
            return new Number(data);
        }

        parseDigitWithoutZero(data.substring(0,1));
        parseDigit(data.substring(1));
        return new Number(data);
    }

    //called by method parseNumber(...)
    //checks if a String only contains numbers(including zero) with parseCharacter(...)
    private void parseDigit(String data) throws ParserException {
        for(int index=1; index<data.length(); index++) {
            String character = Character.toString(data.charAt(index));
            if(!parseCharacter(character, "0123456789")) {
                throw new ParserException("SyntaxError: unexpected character: " + character);
            }
        }
    }

    //called by method parseNumber(...)
    //checks if a String only contains numbers(excluding zero) with parseCharacter(...)
    private void parseDigitWithoutZero(String data) throws ParserException {
        for(int index=1; index<data.length(); index++) {
            String character = Character.toString(data.charAt(index));
            if(!parseCharacter(character, "123456789")) {
                throw new ParserException("SyntaxError: unexpected character: " + character);
            }
        }
    }

    private Boolean parseComma(List<Lexer.Token> ts) throws ParserException {
        String data = ts.get(1).getData();
        if(parseCharacter(data, ".")) {
            if(ts.get(2).getType()!= Lexer.TokenType.NUMBER) {
                throw new ParserException("SyntaxError: no number after comma");
            }
            return true;
        }
        return false;
    }

    private Boolean parseBracket(List<Lexer.Token> ts) throws ParserException {
        String data = ts.get(0).getData();
        if(parseCharacter(data, "(")) {
            return true;
        }
        else {
            return false;
        }
    }

    //called by methods parseOperator(...), parseDigit(...), parseDigitWithoutZero(...)
    //checks if a certain string can be found in a string of allowed character
    private Boolean parseCharacter(String data, String allowedCharacters) throws ParserException {
        if(data.isEmpty()) {
            throw new ParserException("RuntimeError: empty String");
        }
        return (allowedCharacters.contains(data));
    }
}