Pagini recente » Cod sursa (job #2423439) | Cod sursa (job #2159919) | Cod sursa (job #2288504) | Cod sursa (job #3182826) | Cod sursa (job #1439599)
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;
struct Edge{int order, sign, priority, x1, x2, left, right;};
Edge edges[50001];
int id[50001];
int compare(const void *a, const void *b)
{
int comp = -1 * (edges[*(int*)a].priority - edges[*(int*)b].priority);
if (comp != 0)
return comp;
return edges[*(int*)a].order - edges[*(int*)b].order;
}
int makeEdges(char *input)
{
int input_size = strlen(input);
int left_nr = 0;
int sign = 1;
int sign_priority = 1;
int current_priority = 0;
int n = 0;
for (int i = 0; i < input_size; i++)
{
switch(input[i])
{
case '(':
current_priority += 3;
break;
case ')':
current_priority -= 3;
break;
case '+':
sign = 1;
sign_priority = current_priority + 1;
break;
case '-':
sign = 2;
sign_priority = current_priority + 1;
break;
case '*':
sign = 3;
sign_priority = current_priority + 2;
break;
case '/':
sign = 4;
sign_priority = current_priority + 2;
break;
case '%':
sign = 5;
sign_priority = current_priority + 2;
break;
case '^':
sign = 6;
sign_priority = current_priority + 3;
break;
default:
int x = input[i] - '0';
while (input[i+1] >= '0' && input[i+1] <= '9')
{
i++;
x = x * 10 + (input[i] - '0');
}
++n;
edges[n].x1 = left_nr;
edges[n].x2 = x;
edges[n].priority = sign_priority;
edges[n].sign = sign;
edges[n].left = n-1;
edges[n].right = n+1;
edges[n].order = n;
left_nr = x;
break;
}
}
return n;
}
int compute(Edge e)
{
int t;
switch (e.sign)
{
case 1:
t = e.x1 + e.x2;
break;
case 2:
t = e.x1 - e.x2;
break;
case 3:
t = e.x1 * e.x2;
break;
case 4:
t = e.x1 / e.x2;
break;
}
return t;
}
int main()
{
ifstream in("evaluare.in");
ofstream out("evaluare.out");
char input[100002];
in >> input;
int n = makeEdges(input);
for (int i = 1; i <= n; i++)
id[i] = i;
qsort(id+1, n, sizeof(int), compare);
for (int i = 1; i < n; i++)
{
int t = compute(edges[id[i]]);
edges[edges[id[i]].left].x2 = t;
edges[edges[id[i]].left].right = edges[id[i]].right;
edges[edges[id[i]].right].x1 = t;
edges[edges[id[i]].right].left = edges[id[i]].left;
}
out << compute(edges[id[n]]) << '\n';
return 0;
}