Happy New Year!
[ginac.git] / 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-2019 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 = dynallocate<add>(rest_args);
125         ex rest = dynallocate<mul>(rest_base, *_num_1_p);
126         ex ret = dynallocate<add>(args[0], rest);
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 = dynallocate<mul>(rest_args);
136         ex rest = pow(rest_base, *_num_1_p);
137         return dynallocate<mul>(args[0], rest);
138 }
139
140 static ex make_binop_expr(const int binop, const exvector& args)
141 {
142         switch (binop) {
143                 case '+':
144                         return dynallocate<add>(args);
145                 case '-':
146                         return make_minus_expr(args);
147                 case '*':
148                         return dynallocate<mul>(args);
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