ginac/parser/parse_binop_rhs.cpp

   1 /** @file parse_binop_rhs.cpp
   2  *
   3  *  Code to deal with binary operators. */
   4
   5 /*
   6  *  GiNaC Copyright (C) 1999-2016 Johannes Gutenberg University Mainz, Germany
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  21  */
  22
  23 #include "ex.h"
  24 #include "symbol.h"
  25 #include "mul.h"
  26 #include "add.h"
  27 #include "power.h"
  28 #include "operators.h"
  29 #include "parser.h"
  30 #include "lexer.h"
  31 #include "debug.h"
  32
  33 #include <sstream>
  34 #include <stdexcept>
  35
  36 namespace GiNaC {
  37
  38 /// Make a sum or a product.
  39 static ex make_binop_expr(const int binop, const exvector& args);
  40 /// Check if the token is a binary operator.
  41 static inline bool is_binop(const int c);
  42 /// Get the precedence of the pending binary operator.
  43 static int get_tok_prec(const int c);
  44
  45 /// binoprhs: ([+*/^-] primary)*
  46 ex parser::parse_binop_rhs(int expr_prec, ex& lhs)
  47 {
  48         exvector args;
  49         args.push_back(lhs);
  50         int binop = -1, orig_binop = -1;
  51         bool need_sign_flip = false;
  52         while (1) {
  53                 // check if this is a binop
  54                 if (!is_binop(token)) {
  55                         if (args.size() > 1)
  56                                 return make_binop_expr(orig_binop, args);
  57                         else
  58                                 return lhs;
  59                 }
  60
  61                 // Okay, we know this is a binop.
  62                 if (args.size() == 1)
  63                         orig_binop = token;
  64
  65                 binop = token;
  66
  67                 // If this is a binop that binds at least as tightly as
  68                 // the current binop, consume it, otherwise we are done.
  69                 int tok_prec = get_tok_prec(token);
  70                 if (tok_prec < expr_prec) {
  71                         if (args.size() > 1)
  72                                 return make_binop_expr(orig_binop, args);
  73                         else
  74                                 return lhs;
  75                 }
  76
  77                 get_next_tok();  // eat binop
  78
  79                 // Parse the primary expression after the binary operator.
  80                 ex rhs = parse_primary();
  81
  82                 // If binop binds less tightly with rhs than the operator after
  83                 // rhs, let the pending operator take rhs as its lhs.
  84                 int next_prec = get_tok_prec(token);
  85                 if (tok_prec < next_prec)
  86                         rhs = parse_binop_rhs(tok_prec + 1, rhs);
  87
  88                 // previous operator was '+', and current one is '-'
  89                 // (or vice a versa).
  90                 if (need_sign_flip)
  91                         rhs = - rhs;
  92
  93                 args.push_back(rhs);
  94
  95                 // Minimize the number of eval() and ctor calls. This is
  96                 // crucial for a reasonable performance. If the next operator
  97                 // is compatible with the pending one (or the same) don't create
  98                 // the expression and continue collecting operands instead.
  99                 if (binop == token)
 100                         continue;
 101                 else if (binop == '+' && token == '-') {
 102                         need_sign_flip = token != orig_binop;
 103                         continue;
 104                 } else if (binop == '-' && token == '+') {
 105                         need_sign_flip = token != orig_binop;
 106                         continue;
 107                 } else {
 108                         if (args.size() <= 1)
 109                                 bug("binop has " << args.size() << " arguments, expected >= 2");
 110                         lhs = make_binop_expr(orig_binop, args);
 111                         args.clear();
 112                         args.push_back(lhs);
 113                 }
 114         }
 115 }
 116
 117 extern const numeric* _num_1_p;
 118
 119 static ex make_minus_expr(const exvector& args)
 120 {
 121         exvector rest_args;
 122         rest_args.reserve(args.size() - 1);
 123         std::copy(args.begin() + 1, args.end(), std::back_inserter(rest_args));
 124         ex rest_base = (new add(rest_args))->setflag(status_flags::dynallocated);
 125         ex rest = (new mul(rest_base, *_num_1_p))->setflag(status_flags::dynallocated);
 126         ex ret = (new add(args[0], rest))->setflag(status_flags::dynallocated);
 127         return ret;
 128 }
 129
 130 static ex make_divide_expr(const exvector& args)
 131 {
 132         exvector rest_args;
 133         rest_args.reserve(args.size() - 1);
 134         std::copy(args.begin() + 1, args.end(), std::back_inserter(rest_args));
 135         ex rest_base = (new mul(rest_args))->setflag(status_flags::dynallocated);
 136         ex rest = pow(rest_base, *_num_1_p);
 137         return (new mul(args[0], rest))->setflag(status_flags::dynallocated);
 138 }
 139
 140 static ex make_binop_expr(const int binop, const exvector& args)
 141 {
 142         switch (binop) {
 143                 case '+':
 144                         return (new add(args))->setflag(status_flags::dynallocated);
 145                 case '-':
 146                         return make_minus_expr(args);
 147                 case '*':
 148                         return (new mul(args))->setflag(status_flags::dynallocated);
 149                 case '/':
 150                         return make_divide_expr(args);
 151                 case '^':
 152                         if (args.size() != 2)
 153                                 throw std::invalid_argument(
 154                                                 std::string(__func__)
 155                                                 + ": power should have exactly 2 operands");
 156                         return pow(args[0], args[1]);
 157                 default:
 158                         throw std::invalid_argument(
 159                                         std::string(__func__)
 160                                         + ": invalid binary operation: "
 161                                         + char(binop));
 162         }
 163 }
 164
 165 static inline bool is_binop(const int c)
 166 {
 167         switch (c) {
 168                 case '+':
 169                 case '-':
 170                 case '*':
 171                 case '/':
 172                 case '^':
 173                         return true;
 174                 default:
 175                         return false;
 176         }
 177 }
 178
 179 /// Get the precedence of the pending binary operator.
 180 static int get_tok_prec(const int c)
 181 {
 182         switch (c) {
 183                 case '+':
 184                 case '-':
 185                         return 20;
 186                 case '*':
 187                 case '/':
 188                         return 40;
 189                 case '^':
 190                         return 60;
 191                 default:
 192                         return -1;
 193                         // means 'this is not a binary operator'
 194         }
 195 }
 196
 197 } // namespace GiNaC