LLParser.java

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Arrays;

public class Parser {
    public static void main(String[] args) {
        Parser parser =  new Parser("A AND D AND (B OR NOT C) OR NOT C");
        try {
            System.out.println(parser.parse());
        } catch (Exception e) {
            e.printStackTrace();
        }    }


    abstract class Ast{}

    class Expr extends Ast {
        public String name;
        public Expr(String name) {this.name = name;}
        @Override
        public String toString() { return name;}
    }
    class Or extends Ast {
        public Ast left;
        public Ast right;
        public Or(Ast left, Ast right) {this.left = left; this.right = right;}
        @Override
        public String toString() { return "(" + left.toString() + ") OR (" + right.toString() + ")";}
    }
    class And extends Ast {
        public Ast left;
        public Ast right;
        public And(Ast left, Ast right) {this.left = left; this.right = right;}
        @Override
        public String toString() { return "(" + left.toString() + ") AND (" + right.toString() + ")";}
    }
    class Not extends Ast {
        public Ast ast;
        public Not(Ast ast) {this.ast = ast;}
        @Override
        public String toString() { return "NOT (" + ast.toString() + ")";}
    }

    enum Tag {
        AND, OR, NOT, LPAREN, RPAREN, EXPR;
        protected Ast expr;
    }
    class Token {
        public Tag tag;
        public Ast expr;
        public Token(Tag tag) {this.tag = tag;}
        public Token(Tag tag, Ast expr) {this.tag = tag; this.expr = expr;}
        @Override
        public String toString() {
            if (tag == Tag.EXPR) {
                return "EXPR(" + expr.toString() + ")";
            } else {
                return tag.toString();
            }
        }
    }

    class Tokens{
        List<String> tokens;
        public Tokens(String input) {
            this.tokens = new ArrayList<String>(Arrays.asList(input.replaceAll("\\(", " ( ").replaceAll("\\)", " ) ").split(" ")));
        }

        Token toToken(String value) {
            switch(value) {
            case "AND": return new Token(Tag.AND);
            case "OR": return new Token(Tag.OR);
            case "NOT": return new Token(Tag.NOT);
            case "(": return new Token(Tag.LPAREN);
            case ")": return new Token(Tag.RPAREN);
            default: return new Token(Tag.EXPR, new Expr(value));
            }
        }

        public Token next() {
            Token ret = peek();
            tokens.remove(0);
            return ret;
        }
        public Token peek() {
            seek();
            String value = tokens.get(0);
            return toToken(value);
        }

        public boolean hasNext() {
            seek();
            return ! tokens.isEmpty();
        }

        void seek() {
            while (!tokens.isEmpty() && tokens.get(0).equals("")) tokens.remove(0);
        }

        @Override
        public String toString() { return tokens.toString(); }
    }

    Tokens tokens;

    public Parser(String input) {
        tokens = new Tokens(input);
    }


    public Ast parse() throws Exception {
        Ast ret = parseExpr();
        return ret;
    }

    Ast parseExpr() throws Exception {
        Ast elm = parseElm();

        if (!tokens.hasNext()) {
            return elm;
        }
        switch(tokens.peek().tag) {
        case RPAREN:
            return elm;
        case LPAREN:
            tokens.next();
            return parseParen();
        case AND:
            tokens.next();
            return parseAnd(elm);
        case OR:
            tokens.next();
            return parseOr(elm);
        case EXPR:
            return parseElm();
        default:
            throw new Exception();
        }
    }


    Ast parseElm() throws Exception {
        Token tok = tokens.next();
        if (tok.tag == Tag.EXPR) {
            return tok.expr;
        }
        else if (tok.tag == Tag.NOT) {
            return parseNot();
        }
        else if (tok.tag == Tag.LPAREN) {
            return parseParen();
        } else {
            throw new Exception();
        }
    }

    Ast parseParen() throws Exception {
        Ast expr = parseExpr();
        Token rparen = tokens.next();
        if (rparen.tag != Tag.RPAREN) {
            throw new Exception();
        }
        return expr;
    }

    Ast parseAnd(Ast left) throws Exception {
        Ast right = parseExpr();
        return new And(left, right);
    }

    Ast parseOr(Ast left) throws Exception {
        Ast right = parseExpr();
        return new Or(left, right);
    }

    Ast parseNot() throws Exception {
        Ast expr = parseElm();
        return new Not(expr);
    }
}

LRParser.java

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Arrays;

public class Parser {
    public static void main(String[] args) {
        Parser parser = new Parser("A AND D AND (B OR NOT C) OR NOT C");
        try {
            System.out.println(parser.parse());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    abstract class Ast{}

    class Expr extends Ast {
        public String name;
        public Expr(String name) {this.name = name;}
        @Override
        public String toString() { return name;}
    }
    class Or extends Ast {
        public Ast left;
        public Ast right;
        public Or(Ast left, Ast right) {this.left = left; this.right = right;}
        @Override
        public String toString() { return "(" + left.toString() + ") OR (" + right.toString() + ")";}
    }
    class And extends Ast {
        public Ast left;
        public Ast right;
        public And(Ast left, Ast right) {this.left = left; this.right = right;}
        @Override
        public String toString() { return "(" + left.toString() + ") AND (" + right.toString() + ")";}
    }
    class Not extends Ast {
        public Ast ast;
        public Not(Ast ast) {this.ast = ast;}
        @Override
        public String toString() { return "NOT (" + ast.toString() + ")";}
    }

    enum Tag {
        AND, OR, NOT, LPAREN, RPAREN, EXPR;
        protected Ast expr;
    }
    class Token {
        public Tag tag;
        public Ast expr;
        public Token(Tag tag) {this.tag = tag;}
        public Token(Tag tag, Ast expr) {this.tag = tag; this.expr = expr;}
        @Override
        public String toString() {
            if (tag == Tag.EXPR) {
                return "EXPR(" + expr.toString() + ")";
            } else {
                return tag.toString();
            }
        }
    }

    class Tokens{
        List<String> tokens;
        public Tokens(String input) {
            this.tokens = new ArrayList(Arrays.asList(input.replaceAll("\\(", " ( ").replaceAll("\\)", " ) ").split(" ")));
        }

        Token toToken(String value) {
            switch(value) {
            case "AND": return new Token(Tag.AND);
            case "OR": return new Token(Tag.OR);
            case "NOT": return new Token(Tag.NOT);
            case "(": return new Token(Tag.LPAREN);
            case ")": return new Token(Tag.RPAREN);
            default: return new Token(Tag.EXPR, new Expr(value)); 
            }
        }
        
        public Token next() {
            Token ret = peek();
            tokens.remove(0);
            return ret;
        }
        public Token peek() {
            seek();
            String value = tokens.get(0);
            return toToken(value);
        }

        public boolean hasNext() {
            seek();
            return ! tokens.isEmpty();
        }

        void seek() {
            while (!tokens.isEmpty() && tokens.get(0).equals("")) tokens.remove(0);            
        }

        @Override
        public String toString() { return tokens.toString(); }
        
    }

    private Tokens tokens;
    private List<Token> stack;

    public Parser(String input) {
        tokens = new Tokens(input);
        stack = new ArrayList<>();
    }

    Token pop() {
        return stack.remove(0);
    }

    void push(Token tok) {
        stack.add(0, tok);
    }

    Token peek() {
        return stack.get(0);
    }

    Token peek(int n) {
        return stack.get(n);
    }

    boolean isShift() {
        if (0 < stack.size() && peek().tag == Tag.RPAREN) {
            return false;
        }
        switch(tokens.peek().tag) {
        case AND:
        case OR: {
            if (1 < stack.size() && peek(1).tag == Tag.NOT) {
                return false;
            } else {
                return true;
            }
        }
        case RPAREN:
            if (1 < stack.size() && peek(1).tag == Tag.LPAREN) {
                return true;
            } else {
                return false;
            }
        default:
            return true;
        }            
    }

    boolean isReduce() {
        if (peek().tag == Tag.RPAREN) {
            return true;
        } else if (1 < stack.size() && peek(1).tag == Tag.NOT) {
            return true;
        } else if (2 < stack.size() && (peek(1).tag == Tag.AND || peek(1).tag == Tag.OR)) {
            return true;
        } else {
            return false;
        }
    }

    public Ast parse() throws Exception {
        while(tokens.hasNext()) {
            System.out.println(stack);
            System.out.println(tokens);
            if (isShift()) {
                shift();
            } else if (isReduce()) {
                reduce();
            } else {
                throw new Exception();
            }
        }
        while (isReduce()) {
            System.out.println(stack);
            System.out.println(tokens);
            reduce();
        }
        return pop().expr;
    }

    void shift() throws Exception {
        Token tok = tokens.next();
        push(tok);
    }

    void reduce() throws Exception {
        Token tok = pop();
        switch(tok.tag) {
        case RPAREN: {
            Token expr = pop();
            Token lparen = pop();
            if (lparen.tag != Tag.LPAREN) {
                throw new Exception();
            }
            push(expr);
            break;
        }
        case EXPR: {
            Token tok2 = pop();
            switch (tok2.tag) {
            case NOT: {                
                Ast expr = tok.expr;
                push(new Token(Tag.EXPR, new Not(expr)));
                break;
            }
            case AND: {
                Token tok3 = pop();
                if (tok3.tag != Tag.EXPR) {
                    throw new Exception();
                }
                Ast right = tok.expr;
                Ast left = tok3.expr;
                push(new Token(Tag.EXPR, new And(left, right)));
                break;                
            }
            case OR: {
                Token tok3 = pop();
                if (tok3.tag != Tag.EXPR) {
                    System.out.println(tok3);
                    throw new Exception();
                }
                Ast right = tok.expr;
                Ast left = tok3.expr;
                push(new Token(Tag.EXPR, new Or(left, right)));
                break;
            }
            default: {
                throw new Exception();
            }
            }
            break;
        }
        default:
            throw new Exception();
        }
    }    
}