← Back to branch summary

~ubuntu-branches/ubuntu/karmic/kid3/karmic

« back to all changes in this revision

Viewing changes to kid3/expressionparser.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Gabriele Postorino
  • Date: 2008-05-09 03:18:56 UTC
  • mfrom: (1.1.7 upstream) (2.1.3 lenny)
  • Revision ID: james.westby@ubuntu.com-20080509031856-857a3p6l3fv4ir5m
Tags: 1.0-1ubuntu1
https://launchpad.net/bugs/229050
* Merge from debian unstable, (LP: #229050) remaining changes:
  - debian/rules:
    + Added dh_icons
  - debian/control:
    + Update maintainer field.

Show diffs side-by-side

added added

removed removed

Lines of Context:
kid3/expressionparser.cpp
 
1
/**
 
2
 * \file expressionparser.h
 
3
 * Simple parser for expressions.
 
4
 *
 
5
 * \b Project: Kid3
 
6
 * \author Urs Fleisch
 
7
 * \date 23 Jan 2008
 
8
 *
 
9
 * Copyright (C) 2008  Urs Fleisch
 
10
 *
 
11
 * This file is part of Kid3.
 
12
 *
 
13
 * Kid3 is free software; you can redistribute it and/or modify
 
14
 * it under the terms of the GNU General Public License as published by
 
15
 * the Free Software Foundation; either version 2 of the License, or
 
16
 * (at your option) any later version.
 
17
 *
 
18
 * Kid3 is distributed in the hope that it will be useful,
 
19
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
20
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
21
 * GNU General Public License for more details.
 
22
 *
 
23
 * You should have received a copy of the GNU General Public License
 
24
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
25
 *
 
26
 * The RPN tokenizer is based on ExprEvaluator,
 
27
 * Copyright (C) 2004 the VideoLAN team, under the same license.
 
28
 */
 
29
 
 
30
#include "expressionparser.h"
 
31
#include "qtcompatmac.h"
 
32
 
 
33
/**
 
34
 * Constructor.
 
35
 *
 
36
 * @param operators additional operators (besides not, and, or),
 
37
 *                  highest priority first
 
38
 */
 
39
ExpressionParser::ExpressionParser(QStringList operators) :
 
40
        m_operators(operators << "not" << "and" << "or"),
 
41
        m_error(false)
 
42
{
 
43
}
 
44
 
 
45
/**
 
46
 * Destructor.
 
47
 */
 
48
ExpressionParser::~ExpressionParser()
 
49
{
 
50
}
 
51
 
 
52
/**
 
53
 * Compare operator priority.
 
54
 *
 
55
 * @return true if op1 has less priority than op2.
 
56
 */
 
57
bool ExpressionParser::lessPriority(const QString& op1,
 
58
                                                                                                                                                const QString& op2) const
 
59
{
 
60
#if QT_VERSION >= 0x040000
 
61
        int index1 = m_operators.indexOf(op1);
 
62
        int index2 = m_operators.indexOf(op2);
 
63
#else
 
64
        int index1 = m_operators.findIndex(op1);
 
65
        int index2 = m_operators.findIndex(op2);
 
66
#endif
 
67
        if (op1 == "(") return true;
 
68
        if (index1 >= 0 && index2 >= 0) return index1 >= index2;
 
69
        return false;
 
70
}
 
71
 
 
72
/**
 
73
 * Tokenize an expression in reverse polish notation.
 
74
 *
 
75
 * @param expr with strings, operators, not, and, or, (, ).
 
76
 */
 
77
void ExpressionParser::tokenizeRpn(const QString& expr)
 
78
{
 
79
        m_rpnStack.clear();
 
80
 
 
81
        QStringList operatorStack;
 
82
        QString token;
 
83
        int begin = 0, end = 0, len = expr.length();
 
84
        while (begin < len) {
 
85
                // skip spaces
 
86
                while (expr[begin] == ' ') {
 
87
                        ++begin;
 
88
                }
 
89
 
 
90
                if (expr[begin] == '(') {
 
91
                        // push '(' on operator stack and continue
 
92
                        operatorStack.push_back("(");
 
93
                        ++begin;
 
94
                } else if (expr[begin] == ')') {
 
95
                        // after ')', pop operator stack until '(' is found
 
96
                        while (!operatorStack.empty()) {
 
97
                                QString lastOp = operatorStack.back();
 
98
                                operatorStack.pop_back();
 
99
                                if (lastOp == "(") {
 
100
                                        break;
 
101
                                }
 
102
                                m_rpnStack.push_back(lastOp);
 
103
                        }
 
104
                        ++begin;
 
105
                } else {
 
106
                        if (expr[begin] == '"') {
 
107
                                // skip quoted string
 
108
                                end = begin + 1;
 
109
                                while (end < len &&
 
110
                                                         !(expr[end] == '"' && (end <= 0 || expr[end - 1] != '\\'))) {
 
111
                                        ++end;
 
112
                                }
 
113
                                token = expr.mid(begin + 1, end - begin - 1);
 
114
                                token.replace("\\\"", "\"");
 
115
                                begin = end + 1;
 
116
                        } else {
 
117
                                // skip spaces
 
118
                                end = begin;
 
119
                                while (end < len && expr[end] != ' ' && expr[end] != ')') {
 
120
                                        ++end;
 
121
                                }
 
122
                                token = expr.mid(begin, end - begin);
 
123
                                begin = end;
 
124
                        }
 
125
                        if (m_operators.contains(token)) {
 
126
                                // pop the operator stack while the token has lower priority
 
127
                                while (!operatorStack.empty() &&
 
128
                                                         lessPriority(token, operatorStack.back())) {
 
129
                                        QString lastOp = operatorStack.back();
 
130
                                        operatorStack.pop_back();
 
131
                                        m_rpnStack.push_back(lastOp);
 
132
                                }
 
133
                                operatorStack.push_back(token);
 
134
                        } else {
 
135
                                m_rpnStack.push_back(token);
 
136
                        }
 
137
                }
 
138
        }
 
139
        // pop operator stack
 
140
        while (!operatorStack.empty()) {
 
141
                QString lastOp = operatorStack.back();
 
142
                operatorStack.pop_back();
 
143
                m_rpnStack.push_back(lastOp);
 
144
        }
 
145
        m_rpnIterator = m_rpnStack.begin();
 
146
}
 
147
 
 
148
/**
 
149
 * Get the next token from the RPN stack.
 
150
 *
 
151
 * @return token, QString::null if stack is empty.
 
152
 */
 
153
QString ExpressionParser::getToken()
 
154
{
 
155
        if (!m_rpnStack.empty()) {
 
156
                QString token = m_rpnStack.front();
 
157
                m_rpnStack.pop_front();
 
158
                return token;
 
159
        }
 
160
        return QString::null;
 
161
}
 
162
 
 
163
 
 
164
/**
 
165
 * Convert a string to a boolean.
 
166
 *
 
167
 * @param str string
 
168
 * @param b   the boolean is returned here
 
169
 *
 
170
 * @return true if ok.
 
171
 */
 
172
static bool stringToBool(const QString& str, bool& b)
 
173
{
 
174
        if (str == "1" || str == "true" || str == "on" || str == "yes") {
 
175
                b = true;
 
176
                return true;
 
177
        } else if (str == "0" || str == "false" || str == "off" || str == "no") {
 
178
                b = false;
 
179
                return true;
 
180
        }
 
181
        return false;
 
182
}
 
183
 
 
184
/**
 
185
 * Convert a boolean to a string.
 
186
 *
 
187
 * @param b boolean to convert
 
188
 *
 
189
 * @return "1" or "0".
 
190
 */
 
191
static QString boolToString(bool b)
 
192
{
 
193
        return b ? "1" : "0";
 
194
}
 
195
 
 
196
/**
 
197
 * Clear the variable stack before restarting an evaluation.
 
198
 */
 
199
void ExpressionParser::clearEvaluation()
 
200
{
 
201
        m_rpnIterator = m_rpnStack.begin();
 
202
        m_varStack.clear();
 
203
        m_error = false;
 
204
}
 
205
 
 
206
/**
 
207
 * Pop a boolean from the variable stack.
 
208
 * Can be used to get the result after evaluate() returns false and
 
209
 * no error occurred.
 
210
 *
 
211
 * @param var the boolean is returned here
 
212
 *
 
213
 * @return true if ok.
 
214
 */
 
215
bool ExpressionParser::popBool(bool& var)
 
216
{
 
217
        if (m_varStack.empty() || !stringToBool(m_varStack.back(), var)) {
 
218
                return false;
 
219
        }
 
220
        m_varStack.pop_back();
 
221
        return true;
 
222
}
 
223
 
 
224
/**
 
225
 * Push a boolean to the variable stack.
 
226
 * Can be used to push the result of the operation returned by
 
227
 * evaluate() back onto the variable stack.
 
228
 *
 
229
 * @param var boolean to  push
 
230
 */
 
231
void ExpressionParser::pushBool(bool var)
 
232
{
 
233
        m_varStack.push_back(boolToString(var));
 
234
}
 
235
 
 
236
/**
 
237
 * Pop two booleans from the variable stack.
 
238
 *
 
239
 * @param var1 first boolean
 
240
 * @param var2 second boolean
 
241
 *
 
242
 * @return true if ok.
 
243
 */
 
244
bool ExpressionParser::popTwoBools(bool& var1, bool& var2)
 
245
{
 
246
        if (m_varStack.empty() || !stringToBool(m_varStack.back(), var1)) {
 
247
                return false;
 
248
        }
 
249
        m_varStack.pop_back();
 
250
        if (m_varStack.empty() || !stringToBool(m_varStack.back(), var2)) {
 
251
                return false;
 
252
        }
 
253
        m_varStack.pop_back();
 
254
        return true;
 
255
}
 
256
 
 
257
/**
 
258
 * Evaluate the RPN stack.
 
259
 * Boolean operations and, or, not are performed automatically. If another
 
260
 * operation has to be performed, the method stops and returns operator
 
261
 * and variables. The result can then be pushed onto the stack using
 
262
 * pushBool() and then the method can be called again.
 
263
 *
 
264
 * @param op the operator is returned here
 
265
 * @param var1 the first variable is returned here
 
266
 * @param var2 the second variable is returned here
 
267
 *
 
268
 * @return true if the RPN stack has more to evaluate,
 
269
 *         if false, the evaluation is finished.
 
270
 */
 
271
bool ExpressionParser::evaluate(QString& op, QString& var1, QString& var2)
 
272
{
 
273
        while (m_rpnIterator != m_rpnStack.end()) {
 
274
                QString token = *m_rpnIterator++;
 
275
                if (token == "and") {
 
276
                        bool var1, var2;
 
277
                        if (!popTwoBools(var1, var2)) {
 
278
                                m_error = true;
 
279
                                break;
 
280
                        }
 
281
                        pushBool(var1 && var2);
 
282
                } else if (token == "or") {
 
283
                        bool var1, var2;
 
284
                        if (!popTwoBools(var1, var2)) {
 
285
                                m_error = true;
 
286
                                break;
 
287
                        }
 
288
                        pushBool(var1 || var2);
 
289
                } else if (token == "not") {
 
290
                        bool var;
 
291
                        if (!popBool(var)) {
 
292
                                m_error = true;
 
293
                                break;
 
294
                        }
 
295
                        pushBool(!var);
 
296
                } else if (m_operators.contains(token)) {
 
297
                        if (m_varStack.empty()) {
 
298
                                m_error = true;
 
299
                                break;
 
300
                        }
 
301
                        var1 = m_varStack.back();
 
302
                        m_varStack.pop_back();
 
303
                        if (m_varStack.empty()) {
 
304
                                m_error = true;
 
305
                                break;
 
306
                        }
 
307
                        var2 = m_varStack.back();
 
308
                        m_varStack.pop_back();
 
309
                        op = token;
 
310
                        return true;
 
311
                } else {
 
312
                        m_varStack.push_back(token);
 
313
                }
 
314
        }
 
315
        return false;
 
316
}