371 lines
7.0 KiB
C++
371 lines
7.0 KiB
C++
/*
|
|
Copyright 2010-2016 Grégory Soutadé
|
|
|
|
This file is part of KissCount.
|
|
|
|
KissCount 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 3 of the License, or
|
|
(at your option) any later version.
|
|
|
|
KissCount 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 KissCount. If not, see <http://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
#include <string.h>
|
|
#include <stdio.h>
|
|
#include <iostream>
|
|
|
|
#include "ParseExp.hpp"
|
|
|
|
/*
|
|
Algorithm
|
|
The idea of this parser is very simple : Create a binary tree with an operator, a left and a right operand.
|
|
Leafs are constants to be computed. This structure is more flexbile than a simple stack and very easy to parse
|
|
(for resultat computation).
|
|
A simple expression (3+4) will be represented by :
|
|
+
|
|
3 4
|
|
Another example (3+4+5) :
|
|
+
|
|
3 +
|
|
4 5
|
|
|
|
If an operator is less prioritary than his father we have to do a transformation.
|
|
Example with 3*4+5.
|
|
in first instance we may have this tree :
|
|
*
|
|
3 +
|
|
4 5
|
|
So we must reverse the tree into something like :
|
|
+
|
|
* 5
|
|
3 4
|
|
|
|
At each step the parser must read one operand and one operator,
|
|
fill a node with the operator and left operand and recurse on right
|
|
operand. Finally we stop with a constant (a leaf).
|
|
Operations in parenthesis must be computed separatly and filled into
|
|
the tree like constants.
|
|
*/
|
|
|
|
/* Less to most prioritary */
|
|
enum {CST, ADD, SUB, MUL, DIV, MOD, EXP};
|
|
|
|
enum {DOUBLE_POINTED=1, INVALID_CHAR, INVALID_PARENTHESIS, INVALID_OPERATION};
|
|
|
|
|
|
#ifdef DEBUG
|
|
#define P(x) x
|
|
#else
|
|
#define P(x)
|
|
#endif
|
|
|
|
static double atof(char* s, int size)
|
|
{
|
|
int neg = 0;
|
|
double res = 0;
|
|
|
|
for (; size--; s++)
|
|
{
|
|
if (*s == '.')
|
|
{
|
|
neg = 10;
|
|
continue;
|
|
}
|
|
|
|
if (neg > 0)
|
|
{
|
|
res += (double) (*s - '0') / (double)neg;
|
|
neg *= 10;
|
|
}
|
|
else
|
|
{
|
|
res *= 10;
|
|
res += *s - '0';
|
|
}
|
|
}
|
|
|
|
return res;
|
|
}
|
|
|
|
void ParseExp::ParseExp(char** expr, struct parse_opt* root, bool needParenthesis)
|
|
{
|
|
char* temp;
|
|
bool pointed = false;
|
|
struct parse_opt* l, *r, *op, *op_tmp;
|
|
char type = -1;
|
|
bool negative = false, number = false;
|
|
l = r = op = op_tmp = 0;
|
|
|
|
if (!**expr) return;
|
|
|
|
for (temp=*expr; **expr; (*expr)++)
|
|
{
|
|
if (**expr == '(')
|
|
{
|
|
op_tmp = new struct parse_opt;
|
|
op_tmp->type = CST;
|
|
op_tmp->root = root;
|
|
op_tmp->l = op_tmp->r = 0;
|
|
(*expr)++;
|
|
ParseExp(expr, op_tmp, true);
|
|
l = op_tmp;
|
|
root->l = l;
|
|
continue;
|
|
}
|
|
|
|
if (**expr == ')')
|
|
{
|
|
if (!needParenthesis)
|
|
throw INVALID_PARENTHESIS;
|
|
|
|
if ((*expr-temp) == 0)
|
|
throw INVALID_OPERATION;
|
|
break;
|
|
}
|
|
|
|
if (**expr >= '0' && **expr <= '9')
|
|
continue;
|
|
|
|
if (**expr == '.')
|
|
{
|
|
if (!pointed)
|
|
pointed = true;
|
|
else
|
|
throw DOUBLE_POINTED;
|
|
|
|
continue;
|
|
}
|
|
|
|
if (type != -1)
|
|
throw INVALID_OPERATION;
|
|
|
|
switch(**expr)
|
|
{
|
|
case '+':
|
|
type = ADD;
|
|
break;
|
|
case '-':
|
|
if (temp == *expr)
|
|
{
|
|
if (negative)
|
|
throw INVALID_OPERATION;
|
|
temp++;
|
|
negative = true;
|
|
continue;
|
|
}
|
|
type = SUB;
|
|
break;
|
|
case '/':
|
|
type = DIV;
|
|
break;
|
|
case '*':
|
|
type = MUL;
|
|
break;
|
|
// case '%':
|
|
// type = MOD;
|
|
// break;
|
|
default:
|
|
throw INVALID_CHAR;
|
|
}
|
|
|
|
number= true;
|
|
|
|
if (!l)
|
|
{
|
|
if ((*expr-temp) == 0)
|
|
throw INVALID_OPERATION;
|
|
l = new struct parse_opt;
|
|
l->type = CST;
|
|
l->root = root;
|
|
l->l = 0; l->r = 0;
|
|
l->value = atof(temp, *expr-temp);
|
|
if (negative)
|
|
l->value *= -1.0;
|
|
root->l = l;
|
|
}
|
|
|
|
// Here [temp..expr] must be left operand + operator
|
|
if (root->root && root->root->type >= type)
|
|
{
|
|
// Reverse tree
|
|
op = new parse_opt;
|
|
op->root = root->root;
|
|
op->type = root->root->type;
|
|
op->r = l;
|
|
op->l = root->root->l;
|
|
op->l->root = op;
|
|
root->root->l = op;
|
|
root->root->type = type;
|
|
|
|
root->type = CST;
|
|
root->value = 0.0;
|
|
root->l = 0 ; root->r = 0;
|
|
|
|
(*expr)++;
|
|
ParseExp(expr, root, needParenthesis);
|
|
break;
|
|
temp=*expr;
|
|
}
|
|
else
|
|
{
|
|
// Recurse on right operand
|
|
root->type = type;
|
|
// atof
|
|
r = new struct parse_opt;
|
|
r->type = CST;
|
|
r->root = root;
|
|
r->l = 0; r->r = 0;
|
|
r->value = 0.0;
|
|
root->r = r;
|
|
|
|
(*expr)++;
|
|
ParseExp(expr, r, needParenthesis);
|
|
break;
|
|
temp=*expr;
|
|
}
|
|
|
|
}
|
|
|
|
if (needParenthesis && **expr != ')')
|
|
throw INVALID_PARENTHESIS;
|
|
|
|
if (!number)
|
|
{
|
|
if ((*expr-temp) == 0)
|
|
throw INVALID_OPERATION;
|
|
|
|
if (op_tmp)
|
|
*root = *op_tmp;
|
|
else
|
|
{
|
|
root->type = CST;
|
|
root->l = 0; root->r = 0;
|
|
root->value = atof(temp, *expr-temp);
|
|
if (negative)
|
|
root->value *= -1.0;
|
|
}
|
|
}
|
|
|
|
return ;
|
|
}
|
|
|
|
double ParseExp::EvaluateExpr(struct parse_opt* root, bool del)
|
|
{
|
|
double l, r, res;
|
|
char type;
|
|
|
|
type = root->type;
|
|
|
|
if (root->type != CST)
|
|
{
|
|
l = EvaluateExpr(root->l, del);
|
|
r = EvaluateExpr(root->r, del);
|
|
}
|
|
else
|
|
l = root->value;
|
|
|
|
if (del)
|
|
{
|
|
if (root->l) delete root->l;
|
|
if (root->r) delete root->r;
|
|
}
|
|
|
|
switch (type)
|
|
{
|
|
case ADD:
|
|
P(std::cout << "\t" << l << " + " << r << std::endl);
|
|
return l+r;
|
|
case SUB:
|
|
P(std::cout << "\t" << l << " - " << r << std::endl);
|
|
return l-r;
|
|
case MUL:
|
|
P(std::cout << "\t" << l << " * " << r << std::endl);
|
|
return l*r;
|
|
case DIV:
|
|
P(std::cout << "\t" << l << " / " << r << std::endl);
|
|
return l/r;
|
|
// case MOD:
|
|
// return EvaluateExpr(root->l) % EvaluateExpr(root->r);
|
|
case EXP:
|
|
P(std::cout << "\t" << l << " ^ " << r << std::endl);
|
|
res = 1;
|
|
while (r--)
|
|
res *= l;
|
|
return res;
|
|
case CST:
|
|
return l;
|
|
default:
|
|
return 0.0;
|
|
}
|
|
}
|
|
|
|
#ifdef DEBUG
|
|
using namespace ParseExp;
|
|
|
|
static char* e1;
|
|
static inline int test(char* expr, double target_result)
|
|
{
|
|
struct parse_opt root, *r;
|
|
char* e = e1;
|
|
double res;
|
|
|
|
memset(e1, 0, 100);
|
|
strcpy(e1, expr);
|
|
memset(&root, 0, sizeof(root));
|
|
r = &root;
|
|
|
|
ParseExp::ParseExp(&e1, r, false);
|
|
res = EvaluateExpr(&root, true);
|
|
|
|
res *= 100;
|
|
res = ((long)res)/100.0;
|
|
|
|
if (res == target_result)
|
|
std::cout << e << " = " << res << "\n";
|
|
else
|
|
{
|
|
std::cout << e << "(exp) " << target_result << " != " << "(res) " << res << "\n";
|
|
throw "Invalid result !";
|
|
}
|
|
}
|
|
|
|
int main()
|
|
{
|
|
e1 = new char[100] ;
|
|
|
|
try
|
|
{
|
|
test("4*3", 12);
|
|
test("4*3+5", 17);
|
|
test("3+3+3", 9);
|
|
test("3+3+3+3", 12);
|
|
test("4+3*5", 19);
|
|
test("-4+3*5/2", 3.5);
|
|
test("5+-4", 1);
|
|
test("5--4", 9);
|
|
test("4*(3+2)", 20);
|
|
test("(3+2)*4", 20);
|
|
test("4*(3+2)+5", 25);
|
|
test("5+(3+2)*4", 25);
|
|
test("3+(3+(3+3))", 12);
|
|
test("3+(3+(3+(3+3)))*5", 63);
|
|
test("5+(3/(6+8--5)*9)*4", 10.68);
|
|
test("78.83-(.39+6.46+3.54+.23+1.57)", 66.64);
|
|
}
|
|
catch (int e)
|
|
{
|
|
std::cout << "Error " << e << std::endl;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
#endif
|