Pagini recente » Cod sursa (job #3363710) | Cod sursa (job #3364357) | Cod sursa (job #3364325) | Cod sursa (job #3362698) | Cod sursa (job #3363745)
#include <bits/stdc++.h>
const int NMAX = (1 << 17);
const int LMAX = 2;
std::string str;
size_t idx;
char op[4][4] = { "+-", "*/", "^", "" };
struct node
{
int val;
char op;
node *l, *r;
node(int _val = 0, char _op = 0, node *_l = 0, node *_r = 0) : val(_val), op(_op), l(_l), r(_r) {};
} *arb;
// Construction of the expression tree
node *expr(int lev)
{
node *x, *y;
// Treat each operation on a different level
// 0 -> addition and subtraction
// 1 -> multiplication and division
// 2 -> exponentiation or, in this case, the last level
if(lev == LMAX) // Reached the last level, so it's either
{
if(str[idx] == '(') // 1. A new expression defined by the '('
{
++idx; // Skip the '('
x = expr(0); // Evaluate the expression
++idx; // Skip the ')'
}
else // 2. A number (or a variable in other cases)
{
// Parsing and storing the number
for(x = new node(); str[idx] >= '0' && str[idx] <= '9'; ++idx)
{
x->val = x->val * 10 + str[idx] - '0';
}
}
}
else // Still on an operator's level
{
// Parsing each subexpression and checking if we are
// at the current operator's level (loop condition)
// We first parse through the expressions with higher
// priority i. e. higher level (so firstly exponentiation, then multiplication, ...)
for(x = expr(lev + 1); str[idx] && strchr(op[lev], str[idx]); x = y)
{
// Storing the operator with it's left
// child as the current value, and it's right
// as the new operator/value
y = new node(0, str[idx], x, expr(lev + 1));
++idx;
}
}
return x;
}
// Evaluation function
int eval(node *_arb)
{
switch (_arb->op)
{
case '+':
return (eval(_arb->l) + eval(_arb->r));
break;
case '-':
return (eval(_arb->l) - eval(_arb->r));
break;
case '*':
return (eval(_arb->l) * eval(_arb->r));
break;
case '/':
return (eval(_arb->l) / eval(_arb->r));
break;
default:
return _arb->val;
break;
}
}
std::ifstream fin("evaluare.in");
std::ofstream fout("evaluare.out");
int main()
{
std::getline(fin, str);
arb = expr(0);
fout << eval(arb);
return 0;
}