#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
//#include "stack.h"

#define lg_max 100010


typedef unsigned int uint;
 
typedef struct list_head_struct {
	void *data;
	struct list_head_struct *next;
} nod;
 
typedef nod* Stack;
 
int	push(Stack *S, void *elem);	/* adaugarea la stiva */
void	pop(Stack *S);			/* stergerea din stiva, nu intoarce elementul  
							sters */
void*	top(Stack S);			/* elementul din varful stivei */
uint	GetSize(Stack S);			/* numatul de elemente din stiva (pentru 
							implementarea acestei functii se poate face 
							parcurgerea stivei) */
uint	isEmpty(Stack S);			/* testul de stiva goala */
 


void convert (char *in, char *post, int **el, int *lg);
int get_number (char *in, int *j);
int prior (char op);

int eval(char *post, int *elem, int lg, int *error);

int main()
{	
	char in[lg_max], post[lg_max];
	int *elem=NULL, n=0, i=0, rez, error=0;

	FILE *f=fopen("evaluare.in", "r");
	FILE *g=fopen("evaluare.out", "w");


	fgets(in, lg_max, f);
	in[strlen(in)-1]=0;
	
//	puts(in);



	convert(in, post, &elem, &n);

//	printf("nr: %d, poz: %d\n", n, i);

//	for(i=0; i<n; i++)
//		printf("elem sunt: %d\n", elem[i]);

//	n=get_number(in, &i);

//	printf("nr: %d, poz: %d\n", n, i);

//	puts(post);


	rez=eval(post, elem, n, &error);

//	if(error==1)
//		printf("Exp postfix incorecta\n");
//	else
//		printf("Rezultat: %d\n", rez);

	fprintf(g, "%d\n", rez);

	fclose(g);
	

	return 0;
}

void convert(char *in, char *post, int **el, int *lg)
{	int *elem, n, i, k=0, l;
	Stack s=NULL, p;

	n=strlen(in);
	l=*lg; elem=*el;

//	printf("%d ", n);

	for(i=0; i<n; i++)
	{	if(in[i]<='9' && in[i]>='0')
		{	l++;
			elem=(int *) realloc (elem, l*sizeof(int));
			elem[l-1]= get_number (in, &i);
			post[k]='e'; k++;
		}
		else
			switch(in[i])
			{	case '(':
				{	push(&s, &in[i]);
					break;
				}
				case ')':
				{	while(!isEmpty(s) && *(char *)top(s)!='(')
					{	post[k]=*(char *)top(s); k++;
						pop(&s);
					}
					pop(&s);
					break;
				}
				default:
				{	
					while(!isEmpty(s) && 
					 (prior(*(char *)top(s))>=prior (in[i]) &&
					  in[i]!='^') && 
					 *(char *)top(s)!='(' )
					{	post[k]=*(char *)top(s); k++;
						pop(&s);
						
					}
					push(&s, &in[i]);	
				}
			}
	}

	while(s)
	{	post[k]=*(char *)top(s); k++;
		pop(&s);
	}


	*lg=l;
	*el=elem;


}

int eval(char *post, int *elem, int lg, int *error)
{	int k=0, i, t1, t2, *aux, *rez;
	Stack s=NULL;

	for(i=0; i<strlen(post); i++)
	{	if(post[i]=='e')
		{	
			push(&s, &elem[k]); k++;
		}
		else
		{	

			if(isEmpty(s))
				*error=1;

			t2=*(int *) top(s); pop(&s);

			if(isEmpty(s))
				*error=1;
		
			t1=*(int *) top(s); pop(&s);

			rez=(int *) malloc (4);

			switch(post[i])
			{	case '+':
				{	*rez=t1+t2;
					break;
				}	
				case '-':
				{	*rez=t1-t2;
					break;
				}
				case '*':
				{	*rez=t1*t2;
					break;
				}
				case '/':
				{	*rez=t1/t2;
					break;
				}
				case '^':
				{	*rez=pow(t1, t2);
					break;
				}
			}

//			printf("%d %c %d = %d\n", t1, post[i], t2, *rez);

			push(&s, rez);
		}
	}

	t1=*(int *) top (s);
	pop(&s);

	return t1;
}

int get_number (char *in, int *j)
{	int i, n, k=0;
	i=*j;
	n=strlen(in);

	while(in[i]<='9' && in[i]>='0' && i<n)
	{	k=k*10 + in[i]-'0';
		i++;
	}
	i--;

	*j=i;

	return k;
}

int prior (char op)
{	if(op=='+' || op=='-')
		return 1;
	if(op=='*' || op=='/')
		return 2;
	if(op=='^')
		return 3;
	if(op=='(' || op ==')')
		return 10;
}




int push (Stack *S, void *elem)
{	Stack nou;

	nou=(nod *) malloc (sizeof(nod));
	if(nou==NULL)
		return 0;

	nou->data=elem;
	nou->next=*S;
	*S=nou;

	return 1;
}

void pop(Stack *S)
{	Stack old;
	
	if(*S!=NULL)
	{	old=*S;
		*S=old->next;
		free(old);
	}

}

void* top(Stack S)
{	if(S!=NULL)
		return S->data;
}

uint GetSize(Stack S)
{	Stack p=S;
	uint dim=0;
	while(p)
	{	dim++;
		p=p->next;
	}
	return dim;
}

uint isEmpty(Stack S)
{	if(S==NULL)
		return 1;
	return 0;
}