code: ///////////////////////////////////////////////////////////////////////////////
  // For information as to what this class does, see the Javadoc, below.       //
  // Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,       //
  // 2007, 2008, 2009, 2010, 2014, 2015 by Peter Spirtes, Richard Scheines, Joseph   //
  // Ramsey, and Clark Glymour.                                                //
  //                                                                           //
  // This program is free software; you can redistribute it and/or modify      //
  // it under the terms of the GNU General Public License as published by      //
  // the Free Software Foundation; either version 2 of the License, or         //
  // (at your option) any later version.                                       //
  //                                                                           //
  // This program is distributed in the hope that it will be useful,           //
  // but WITHOUT ANY WARRANTY; without even the implied warranty of            //
  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             //
  // GNU General Public License for more details.                              //
  //                                                                           //
  // You should have received a copy of the GNU General Public License         //
  // along with this program; if not, write to the Free Software               //
  // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA //
  ///////////////////////////////////////////////////////////////////////////////
  
  package edu.cmu.tetrad.calculator.parser;
  
  import edu.cmu.tetrad.calculator.expression.*;
  
  import java.text.ParseException;
  import java.util.*;
  
  /**
   * Parses a string into a tree-like expression.
   *
   * @author Tyler Gibson
   */
  public class ExpressionParser {
  
      /**
       * The type of restriction on parameters. It's either the case that the expression may only contain parameters
       * in the given list, or may not contain parameters in the given list, or that there is no restribution--whatever
       * parameters occur in the expression are OK.
       */
      public enum RestrictionType {
          MAY_ONLY_CONTAIN, MAY_NOT_CONTAIN, NONE
      }
  
  
      /**
       * The getModel token.
       */
      private Token token;
  
  
      /**
       * The lexer.
       */
      private ExpressionLexer lexer;
  
  
      /**
       * The expressin manager used to get the actual expressions from.
       */
      private ExpressionManager expressions = ExpressionManager.getInstance();
  
      /**
       * The parameters read from the string.
       */
      private Set<String> parameters;
  
  
      /**
       * The parameters that are allowed in an expression.
       */
      private Set<String> restrictionParameters;
  
      /**
       * The type of restribution on parameters.
       */
      private RestrictionType restrictionType;
  
  
      /**
       * Constructrs a parser that has no allowable parameters.
       */
      public ExpressionParser() {
          this.restrictionParameters = Collections.emptySet();
          this.parameters = new LinkedHashSet<>();
      }
  
  
      /**
       * Constructs the parser given a collection of allowable parameters.
       */
      public ExpressionParser(Collection<String> parameters, RestrictionType type) {
          if (parameters == null) {
              throw new NullPointerException("Parameters null.");
          }
  
          if (parameters.contains("$")) {
              throw new IllegalArgumentException("Variable list must not " +
                      "contain the wildcard '$'.");
          }
  
          this.restrictionParameters = new LinkedHashSet<>(parameters);
          this.restrictionParameters.add("$");
          this.parameters = new LinkedHashSet<>();
          this.restrictionType = type;
      }
  
      //================================ Public methods ===================================//
  
  
      /**
       * Parses the given expression, or throws an exception if its not possible.
       */
      public Expression parseExpression(String expression) throws ParseException {
          this.lexer = new ExpressionLexer(expression);
          nextToken();
          Expression exp = parseExpression();
          expect(Token.EOF);
          return exp;
      }
  
  
      /**
       * Parses an equation of the form Variable = Expression.
       */
      public Equation parseEquation(String equation) throws ParseException {
          int index = equation.indexOf("=");
          if (index < 1) {
              throw new ParseException("Equations must be of the form Var = Exp", 0);
          }
          String variable = equation.substring(0, index).trim();
          if (!variable.matches("[^0-9]?[^ \t]*")) {
              throw new ParseException("Invalid variable name.", 1);
          }
  
          return new Equation(variable, parseExpression(equation.substring(index + 1).trim()), equation);
      }
  
      public int getNextOffset() {
          return lexer.getNextOffset();
      }
  
      //================================ Private Methods =================================//
  
  
      /**
       * Moves to the next token.
       */
      private void nextToken() throws ParseException {
          this.token = this.lexer.nextToken();
  
          if (this.token == Token.UNKNOWN) {
              throw new ParseException("Unrecognized token,", this.lexer.getCurrentOffset());
          }
      }
  
      /**
       * Parses the expression.
       */
      private Expression parseExpression() throws ParseException {
  //        return parsePlusExpression();
          return parseAndExpression();
      }
  
      private Expression parseAndExpression() throws ParseException {
          Expression expression = parseOrExpression();
  
          while (token == Token.OPERATOR && "AND".equals(lexer.getTokenString())) {
              int offset = lexer.getCurrentOffset();
  
              ExpressionDescriptor descriptor = getDescriptor();
              nextToken();
              Expression expression2 = parseOrExpression();
  
              try {
                  expression = descriptor.createExpression(expression, expression2);
              } catch (ExpressionInitializationException e) {
                  // Should never be thrown.
                  throw new ParseException("Wrong number of arguments for expression " + descriptor.getName(),
                          offset);
              }
          }
  
          return expression;
      }
  
      private Expression parseOrExpression() throws ParseException {
          Expression expression = parseXorExpression();
  
          while (token == Token.OPERATOR && "OR".equals(lexer.getTokenString())) {
              int offset = lexer.getCurrentOffset();
  
              ExpressionDescriptor descriptor = getDescriptor();
              nextToken();
              Expression expression2 = parseXorExpression();
  
              try {
                  expression = descriptor.createExpression(expression, expression2);
              } catch (ExpressionInitializationException e) {
                  // Should never be thrown.
                  throw new ParseException("Wrong number of arguments for expression " + descriptor.getName(),
                          offset);
              }
          }
  
          return expression;
      }
  
      private Expression parseXorExpression() throws ParseException {
          Expression expression = parseComparisonExpression();
  
          while (token == Token.OPERATOR && "XOR".equals(lexer.getTokenString())) {
              int offset = lexer.getCurrentOffset();
  
              ExpressionDescriptor descriptor = getDescriptor();
              nextToken();
              Expression expression2 = parsePlusExpression();
  
              try {
                  expression = descriptor.createExpression(expression, expression2);
              } catch (ExpressionInitializationException e) {
                  // Should never be thrown.
                  throw new ParseException("Wrong number of arguments for expression " + descriptor.getName(),
                          offset);
              }
          }
  
          return expression;
      }
  
      private Expression parseComparisonExpression() throws ParseException {
          Expression expression = parsePlusExpression();
          Set<String> comparisonOperators = new HashSet<>();
          comparisonOperators.add("<");
          comparisonOperators.add("<=");
          comparisonOperators.add("=");
          comparisonOperators.add(">");
          comparisonOperators.add(">=");
  
          while (token == Token.OPERATOR && comparisonOperators.contains(lexer.getTokenString())) {
              int offset = lexer.getCurrentOffset();
  
              ExpressionDescriptor descriptor = getDescriptor();
              nextToken();
              Expression expression2 = parsePlusExpression();
  
              try {
                  expression = descriptor.createExpression(expression, expression2);
              } catch (ExpressionInitializationException e) {
                  // Should never be thrown.
                  throw new ParseException("Wrong number of arguments for expression " + descriptor.getName(),
                          offset);
              }
          }
  
          return expression;
      }
  
  
      private Expression parsePlusExpression() throws ParseException {
          Expression expression = parseMultDivExpression();
  
          while (token == Token.OPERATOR && "+".equals(lexer.getTokenString()) || "-".equals(lexer.getTokenString())) {
              int offset = lexer.getCurrentOffset();
  
              ExpressionDescriptor descriptor = getDescriptor();
              nextToken();
              Expression expression2 = parseMultDivExpression();
  
              try {
                  expression = descriptor.createExpression(expression, expression2);
              } catch (ExpressionInitializationException e) {
                  // Should never be thrown.
                  throw new ParseException("Wrong number of arguments for expression " + descriptor.getName(),
                          offset);
              }
          }
  
          return expression;
      }
  
      private Expression parseMultDivExpression() throws ParseException {
          Expression expression = parsePowerExpression();
  
          while (token == Token.OPERATOR && "*".equals(lexer.getTokenString()) || "/".equals(lexer.getTokenString())) {
              int offset = lexer.getCurrentOffset();
  
              ExpressionDescriptor descriptor = getDescriptor();
              nextToken();
              Expression expression2 = parsePowerExpression();
  
              try {
                  expression = descriptor.createExpression(expression, expression2);
              } catch (ExpressionInitializationException e) {
                  // Should never be thrown.
                  throw new ParseException("Wrong number of arguments for expression " + descriptor.getName(),
                          offset);
              }
          }
  
          return expression;
      }
  
      private Expression parsePowerExpression() throws ParseException {
          Expression expression = parseChompExpression();
  
          while (token == Token.OPERATOR && "^".equals(lexer.getTokenString())) {
              int offset = lexer.getCurrentOffset();
  
              ExpressionDescriptor descriptor = getDescriptor();
              nextToken();
              Expression expression2 = parseChompExpression();
  
              try {
                  expression = descriptor.createExpression(expression, expression2);
              } catch (ExpressionInitializationException e) {
                  // Should never be thrown.
                  throw new ParseException("Wrong number of arguments for expression " + descriptor.getName(),
                          offset);
              }
          }
  
          return expression;
      }
  
  
      /**
       * Chomps an expression.
       */
      private Expression parseChompExpression() throws ParseException {
          int chompOffset = lexer.getCurrentOffset();
          String chompTokenString = lexer.getTokenString();
  
          // parse a number.
          if (token == Token.NUMBER) {
              String numberString = lexer.getTokenString();
  
              // The parseNumber will throw a parse exception.
              Expression exp = new ConstantExpression(convertNumber(numberString));
              nextToken();
              return exp;
          }
  
          // parse a variable.
          if (token == Token.PARAMETER) {
              if (lexer.getTokenString().equals("pi") || lexer.getTokenString().equals("PI")) {
                  nextToken();
                  return ConstantExpression.PI;
              }
  
              if (lexer.getTokenString().equals("e") || lexer.getTokenString().equals("E")) {
                  nextToken();
                  return ConstantExpression.E;
              }
  
              String stringToken = this.lexer.getTokenString();
              if (getRestrictionType() == RestrictionType.MAY_ONLY_CONTAIN) {
                  if (!this.restrictionParameters.contains(stringToken)) {
                      throw new ParseException("Variable " + stringToken + " is not known.", chompOffset);
                  }
              } else if (getRestrictionType() == RestrictionType.MAY_NOT_CONTAIN) {
                  if (this.restrictionParameters.contains(stringToken)) {
                      throw new ParseException("Variable " + stringToken + " may not be used in this expression.", chompOffset);
                  }
              }
  
              this.parameters.add(stringToken);
              VariableExpression exp = new VariableExpression(stringToken);
              nextToken();
              if (this.token == Token.EQUATION) {
                  return parseEvaluation(exp);
              }
  
              return exp;
          }
  
          // deal with prefix operator.
          if (token == Token.OPERATOR) {
              ExpressionDescriptor descriptor = getDescriptor();
              nextToken();
              Expression[] expressions;
  
              if (token == Token.LPAREN) {
                  nextToken();
                  if (token == Token.RPAREN) {
                      nextToken();
                      expressions = new Expression[0];
                  } else {
                      List<Expression> expressionList = parseExpressionList();
                      expect(Token.RPAREN);
                      expressions = expressionList.toArray(new Expression[expressionList.size()]);
                  }
              } else if ("+".equals(chompTokenString) || "-".equals(chompTokenString)) {
                  List<Expression> expressionList = parseSingleExpression();
                  expressions = expressionList.toArray(new Expression[expressionList.size()]);
              } else {
                  throw new ParseException("Expecting a parenthesized list of arguments.", chompOffset);
              }
  
              try {
                  return descriptor.createExpression(expressions);
              } catch (ExpressionInitializationException e) {
                  throw new ParseException("Wrong number of arguments: " + expressions.length + " " + token, chompOffset);
              }
  
          }
  
          // deal with parens.
          if (token == Token.LPAREN) {
              nextToken();
              Expression exp = parseExpression();
              expect(Token.RPAREN);
              return exp;
          }
  
          throw new ParseException("Unexpected token: " + lexer.getTokenString(), this.lexer.getCurrentOffset());
      }
  
  
      /**
       * Creates an evaluation expression.
       */
      private Expression parseEvaluation(VariableExpression variable) throws ParseException {
          expect(Token.EQUATION);
          if (token != Token.STRING) {
              throw new ParseException("Evaluations must be of the form Var = String", lexer.getCurrentOffset());
          }
          String s = lexer.getTokenString();
          nextToken();
          return new EvaluationExpression(variable, s.replace("\"", ""));
      }
  
  
      /**
       * Pareses a comma seperated list of expressions.
       */
      private List<Expression> parseExpressionList() throws ParseException {
          List<Expression> expressions = new LinkedList<>();
  
          expressions.add(parseExpression());
          while (token == Token.COMMA) {
              nextToken();
              expressions.add(parseExpression());
          }
  
          return expressions;
      }
  
      /**
       * Pareses a comma seperated list of expressions.
       */
      private List<Expression> parseSingleExpression() throws ParseException {
          List<Expression> expressions = new LinkedList<>();
          expressions.add(parseExpression());
          return expressions;
      }
  
      private double convertNumber(String number) throws ParseException {
          try {
              return Double.parseDouble(number);
          } catch (Exception ex) {
              throw new ParseException("Not a number: " + number + ".", lexer.getCurrentOffset());
          }
      }
  
  
      /**
       * @return the descriptor represented by the getModel token or throws an exception if there isn't one.
       */
      private ExpressionDescriptor getDescriptor() throws ParseException {
          String tokenString = lexer.getTokenString();
          ExpressionDescriptor descriptor = this.expressions.getDescriptorFromToken(tokenString);
          if (descriptor == null) {
              throw new ParseException("Not a function name: " + tokenString, lexer.getCurrentOffset());
          }
          return descriptor;
      }
  
  
      /**
       * Expects the given token and then reads the next token.
       */
      private void expect(Token token) throws ParseException {
          if (token != this.token) {
              throw new ParseException("Unexpected token: " + getTokenString(), this.lexer.getCurrentOffset());
          }
          nextToken();
      }
  
  
      private RestrictionType getRestrictionType() {
          return restrictionType;
      }
  
      public List<String> getParameters() {
          return new LinkedList<>(parameters);
      }
  
      private String getTokenString() {
          return this.lexer.getTokenString();
      }
  }
  
  
  
  