Pagini recente » Cod sursa (job #2083646) | Cod sursa (job #1691944) | Cod sursa (job #711948) | Cod sursa (job #570009) | Cod sursa (job #2033438)
#include <fstream>
#include <stack>
#include <cstring>
using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");
const int MAX = 1e5 + 1;
char s[MAX];
char *p = s;
bool isOperator(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/';
}
int Priority(char c)
{
switch(c)
{
case '-':
case '+': return 0;
case '/':
case '*': return 1;
case '(': return -1;
}
}
struct Element
{
int value;
bool isOperator;
};
Element fp[MAX];
char operators[2][3] = { "+-", "/*" };
const int maxLevel = 2;
int DoOperator(int first, int second, char c)
{
switch (c)
{
case '+': return first + second;
case '-': return first - second;
case '*': return first * second;
case '/': return first / second;
}
}
struct Node
{
int val;
char oper;
Node* left,* right;
Node(int v = 0, char op = 0, Node* ll = nullptr, Node* rr = nullptr) : val(v), oper(op), left(ll), right(rr) {}
};
Node* BuildTree(int lev)
{
if (lev == maxLevel)
{
if (*p == '(')
{
p++;
Node * node = BuildTree(0);
p++;
return node;
}
else
{
int r = 0;
while (*p >= '0' && *p <= '9')
{
r = r * 10 + *p - '0';
p++;
}
Node * node = new Node(r, 0, nullptr, nullptr);
return node;
}
}
else
{
Node *node = BuildTree(lev + 1);
while (*p && strchr(operators[lev], *p))
{
char op = *p++;
Node *opNode = new Node(0, op, node, BuildTree(lev + 1));
node = opNode;
}
return node;
}
}
int EvalTree(Node* root)
{
if (root->left == nullptr && root->right == nullptr)
{
return root->val;
}
else
{
return DoOperator(EvalTree(root->left), EvalTree(root->right), root->oper);
}
}
int LevelEval(int lev)
{
int r = 0;
if (lev == maxLevel)
{
if (*p == '(')
{
p++;
r = LevelEval(0);
p++;
}
else
{
while (*p >= '0' && *p <= '9')
{
r = r * 10 + *p - '0';
p++;
}
}
}
else
{
r = LevelEval(lev + 1);
while (*p && strchr(operators[lev], *p))
{
char op = *p++;
r = DoOperator(r, LevelEval(lev + 1), op);
}
}
return r;
}
int Eval();
int Factor()
{
int f = 0;
if (*p == '(')
{
++p;
f = Eval();
p++;
}
else
{
while (*p >= '0' && *p <= '9')
{
f = f * 10 + *p - '0';
p++;
}
}
return f;
}
int Termen()
{
int f = Factor();
while (*p == '*' || *p == '/')
{
int c = *p; p++;
if (c == '*')
{
f *= Factor();
}
else if (c == '/')
{
f /= Factor();
}
}
return f;
}
int Eval()
{
int t = Termen();
while (*p == '+' || *p == '-')
{
int c = *p; p++;
if (c == '+')
{
t += Termen();
}
else if (c == '-')
{
t -= Termen();
}
}
return t;
}
int EvalStack(char *s, int len)
{
stack<char> operatori;
int k = 0;
for (int i = 0; i < len; i++)
{
char c = s[i];
if (c == '(')
{
operatori.push(s[i]);
}
else if (isOperator(c))
{
while (!operatori.empty() && Priority(c) <= Priority(operatori.top()))
{
Element el;
el.value = operatori.top();
el.isOperator = true;
operatori.pop();
fp[k++] = el;
}
operatori.push(c);
}
else if (c == ')')
{
while (operatori.top() != '(')
{
Element el;
el.value = operatori.top();
el.isOperator = true;
operatori.pop();
fp[k++] = el;
}
operatori.pop();
}
else
{
int number = c - '0';
i++;
while (i < len && s[i] >= '0' && s[i] <= '9')
{
number = number * 10 + (s[i] - '0');
i++;
}
i--;
Element el;
el.value = number;
el.isOperator = false;
fp[k++] = el;
}
}
while (!operatori.empty())
{
Element el;
el.value = operatori.top();
el.isOperator = true;
operatori.pop();
fp[k++] = el;
}
stack<int> operanzi;
for (int i = 0; i < k; i++)
{
if (fp[i].isOperator)
{
int op1 = operanzi.top();
operanzi.pop();
int op2 = operanzi.top();
operanzi.pop();
double rez = 0;
switch (fp[i].value)
{
case '-': rez = op2 - op1;
break;
case '+': rez = op1 + op2;
break;
case '*': rez = op1 * op2;
break;
case '/': rez = (double)op2 / op1;
break;
}
operanzi.push(rez);
}
else
{
operanzi.push(fp[i].value);
}
}
return operanzi.top();
}
int main()
{
in >> s;
int len = strlen(s);
//out << EvalS tack(s, len) << endl;
//out << LevelEval(0) << endl;
out << EvalTree(BuildTree(0));
}