Pagini recente » Cod sursa (job #1516501) | Cod sursa (job #46109) | Cod sursa (job #1950922) | Cod sursa (job #3125625) | Cod sursa (job #1328862)
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct element
{
char type;
union value
{
char op;
int nr;
} val;
};
struct node
{
element elem;
struct node *left, *right;
};
stack<node*> stn;
stack<char> st;
vector<element> infix, postfix;
short priority[257];
bool isoperator (char x)
{
if (x == '+' || x == '-' || x == '*' || x == '/' || x == '%')
return true;
return false;
}
bool isoperand (char x)
{
if (x >= '0' && x <= '9')
return true;
return false;
}
void infix2postfix()
{
element t;
for (unsigned i = 0; i < infix.size(); ++i)
{
if (infix[i].type == '0')
{
t.type = '0';
t.val.nr = infix[i].val.nr;
postfix.push_back(t);
continue;
}
if (infix[i].type == '(')
{
st.push('(');
continue;
}
if (infix[i].type == ')')
{
while (!st.empty() && st.top() != '(')
{
t.type = 'o';
t.val.op = st.top();
st.pop();
postfix.push_back(t);
}
st.pop();
continue;
}
if (infix[i].type == 'o')
{
t.type = 'o';
if (!st.empty())
{
while (!st.empty() && priority[(int)st.top()] >= priority[(int)infix[i].val.op])
{
t.val.op = st.top();
st.pop();
postfix.push_back(t);
}
}
st.push(infix[i].val.op);
}
}
while (!st.empty())
{
t.type = 'o';
t.val.op = st.top();
st.pop();
postfix.push_back(t);
}
}
node *top()
{
node *n;
if (stn.empty())
return NULL;
n = stn.top();
stn.pop();
return n;
}
node * expr2tree ()
{
node *op1, *op2, *newnode;
for (unsigned i = 0; i < postfix.size(); ++i)
{
if (postfix[i].type == '0')
{
newnode = new node;
newnode -> elem.type = '0';
newnode -> elem.val.nr = postfix[i].val.nr;
newnode -> left = NULL;
newnode -> right = NULL;
stn.push(newnode);
}
else
{
op1 = top();
op2 = top();
newnode = new node;
newnode -> elem.type = 'o';
newnode -> elem.val.op = postfix[i].val.op;
newnode -> left = op2;
newnode -> right = op1;
stn.push(newnode);
}
}
return stn.top();
}
int evaluateTree (node *n)
{
if (n == NULL)
return 0;
if (n -> elem.type == 'o')
{
int op1 = evaluateTree(n->left);
int op2 = evaluateTree(n->right);
switch (n -> elem.val.op)
{
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
}
}
return n -> elem.val.nr;
}
void string2expr (string s)
{
char *p = &s[0];
element t;
while (*p != 0 && *p != '\n')
{
if (isoperand(*p))
{
int x = *p - '0';
++p;
while (isoperand(*p))
{
x = x * 10 + *p - '0';
++p;
}
t.type = '0';
t.val.nr = x;
infix.push_back(t);
}
if (isoperator(*p))
{
t.type = 'o';
t.val.op = *p;
infix.push_back(t);
++p;
}
if (*p == '(' || *p == ')')
{
t.type = *p;
t.val.op = *p;
infix.push_back(t);
++p;
}
}
}
void postorder (node *n)
{
if (n == NULL)
return;
if (n->elem.type == 'o')
cerr << n->elem.val.op;
else
cerr << n->elem.val.nr;
postorder (n->left);
postorder (n->right);
}
int main()
{
ifstream in("evaluare.in");
ofstream out("evaluare.out");
string expr_string;
in >> expr_string;
string2expr(expr_string);
expr_string.clear();
priority['+'] = 1;
priority['-'] = 1;
priority['*'] = 2;
priority['/'] = 2;
priority['('] = 0;
infix2postfix();
node *root;
root = expr2tree();
out << evaluateTree(root) << '\n';
return 0;
}