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-2024 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 /// unary_expr: [+-] expression
 118 ex parser::parse_unary_expr()
 119 {
 120         // Parse a binary expression with the priority of exponentiation
 121         // or higher. Ignore the overall sign, because parse_primary()
 122         // handles it for us.
 123         get_next_tok(); // Skip [+-]
 124         ex lhs = parse_primary();
 125         ex e = parse_binop_rhs(get_tok_prec('^'), lhs);
 126         return e;
 127 }
 128
 129 extern const numeric* _num_1_p;
 130
 131 static ex make_minus_expr(const exvector& args)
 132 {
 133         exvector rest_args;
 134         rest_args.reserve(args.size() - 1);
 135         std::copy(args.begin() + 1, args.end(), std::back_inserter(rest_args));
 136         ex rest_base = dynallocate<add>(rest_args);
 137         ex rest = dynallocate<mul>(rest_base, *_num_1_p);
 138         ex ret = dynallocate<add>(args[0], rest);
 139         return ret;
 140 }
 141
 142 static ex make_divide_expr(const exvector& args)
 143 {
 144         exvector rest_args;
 145         rest_args.reserve(args.size() - 1);
 146         std::copy(args.begin() + 1, args.end(), std::back_inserter(rest_args));
 147         ex rest_base = dynallocate<mul>(rest_args);
 148         ex rest = pow(rest_base, *_num_1_p);
 149         return dynallocate<mul>(args[0], rest);
 150 }
 151
 152 static ex make_power_expr(const exvector& args)
 153 {
 154         size_t n = args.size();
 155         ex p = pow(args[n - 2], args[n - 1]);
 156         for (size_t i = n - 2; i > 0; i--) {
 157                 p = pow(args[i - 1], p);
 158         }
 159         return p;
 160 }
 161
 162 static ex make_binop_expr(const int binop, const exvector& args)
 163 {
 164         switch (binop) {
 165                 case '+':
 166                         return dynallocate<add>(args);
 167                 case '-':
 168                         return make_minus_expr(args);
 169                 case '*':
 170                         return dynallocate<mul>(args);
 171                 case '/':
 172                         return make_divide_expr(args);
 173                 case '^':
 174                         return make_power_expr(args);
 175                 default:
 176                         throw std::invalid_argument(
 177                                         std::string(__func__)
 178                                         + ": invalid binary operation: "
 179                                         + char(binop));
 180         }
 181 }
 182
 183 static inline bool is_binop(const int c)
 184 {
 185         switch (c) {
 186                 case '+':
 187                 case '-':
 188                 case '*':
 189                 case '/':
 190                 case '^':
 191                         return true;
 192                 default:
 193                         return false;
 194         }
 195 }
 196
 197 /// Get the precedence of the pending binary operator.
 198 static int get_tok_prec(const int c)
 199 {
 200         switch (c) {
 201                 case '+':
 202                 case '-':
 203                         return 20;
 204                 case '*':
 205                 case '/':
 206                         return 40;
 207                 case '^':
 208                         return 60;
 209                 default:
 210                         return -1;
 211                         // means 'this is not a binary operator'
 212         }
 213 }
 214
 215 } // namespace GiNaC