Pagini recente » Cod sursa (job #146392) | Cod sursa (job #1722860) | Cod sursa (job #1982750) | Cod sursa (job #1299522) | Cod sursa (job #1276286)
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <stack>
#include <algorithm>
#define Nmax 300001
using namespace std;
struct Node
{
int val;
bool is_op;
Node *left, *right;
};
int priority(char x)
{
switch (x)
{
case '+' : return 1;
case '-' : return 1;
case '*' : return 2;
case '/' : return 2;
default: return 3;
}
}
char* getPostfix(char* s)
{
int sz = strlen(s), cnt = 0;
char res[Nmax];
bool is_number = false;
stack<char> S;
for(int i=0;i<sz;++i)
{
if(s[i] == '\n')
continue;
if(s[i] >= '0' && s[i] <= '9')
{
res[cnt++] = s[i];
is_number = true;
} else {
if(is_number)
{
res[cnt++] = ' ';
is_number = false;
}
if(s[i] == '(')
{
S.push('(');
continue;
}
if(s[i] == ')')
{
while(S.top() != '(')
{
res[cnt++] = S.top();
S.pop();
}
S.pop();
continue;
}
while(!S.empty() && S.top() != '(' && priority(S.top()) >= priority(s[i]))
{
res[cnt++] = S.top();
S.pop();
}
S.push(s[i]);
}
}
while(!S.empty())
{
res[cnt++] = S.top();
S.pop();
}
return res;
}
Node* createExpTree(char* postfix)
{
int sz = strlen(postfix), nr = 0;
bool is_number = false;
stack<Node*> S;
for(int i=0;i<sz;++i)
{
if(postfix[i] >= '0' && postfix[i] <= '9')
{
nr = nr * 10 + (postfix[i] - '0');
is_number = true;
}
else
{
if(is_number)
{
Node*p = new Node;
p->val = nr;
p->is_op = false;
p->left = NULL;
p->right = NULL;
S.push(p);
is_number = false;
nr = 0;
}
if(postfix[i] == ' ')
continue;
Node*p = new Node;
p->val = postfix[i];
p->is_op = true;
p->right = S.top(); S.pop();
p->left = S.top(); S.pop();
S.push(p);
}
}
return S.top();
}
void postorder(Node *p)
{
if(p->left != NULL)
postorder(p->left);
if(p->right != NULL)
postorder(p->right);
if(p->is_op)
cout<<char(p->val)<<" ";
else
cout<<p->val<<" ";
}
int evaluate(Node *p)
{
if(p->is_op)
{
int left = evaluate(p->left);
int right = evaluate(p->right);
switch (p->val)
{
case '+' : return left + right;
case '-' : return left - right;
case '*' : return left * right;
case '/' : return left / right;
}
}
else return p->val;
}
int main()
{
char buf[Nmax];
ifstream f("evaluare.in");
f.getline(buf, Nmax);
f.close();
Node *R = createExpTree(getPostfix(buf));
ofstream g("evaluare.out");
g<<evaluate(R);
g.close();
return 0;
}