#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

// basic lexing

typedef
enum TokenType {TOKEN_PLUS=0, TOKEN_MINUS=1, TOKEN_MULTIPLY=2, TOKEN_DIVIDE=3, TOKEN_POWER=4, TOKEN_EOF, TOKEN_END_OF_LINE, TOKEN_INTEGER}
TokenType;

int precedence[5]={0, 0, 1, 1, 2};
int left_associative[5]={1, 1, 1, 1, 0};

typedef struct Token
{
   TokenType type;
   long long int value; // only applicable for TOKEN_INTEGER
} Token;

Token int_token(long long int v)
{
   Token t={TOKEN_INTEGER, v};
   return t;
}

void print_token(Token *t)
{
   switch(t->type){
      case TOKEN_PLUS:
         printf("plus");
         break;
      case TOKEN_MINUS:
         printf("minus");
         break;
      case TOKEN_MULTIPLY:
         printf("multiply");
         break;
      case TOKEN_DIVIDE:
         printf("divide");
         break;
      case TOKEN_POWER:
         printf("power");
         break;
      case TOKEN_EOF:
         printf("eof");
         break;
      case TOKEN_END_OF_LINE:
         printf("eol");
         break;
      case TOKEN_INTEGER:
         printf("%lld", t->value);
         break;
   }
}

void read_integer(FILE *in, long long int *r)
{
   int c;
   *r=0;
   for(;;){
      c=fgetc(in);
      if(c>='0' && c<='9'){
         *r=*r*10+(c-'0');
      }else{
         ungetc(c, in);
         return;
      }
   }
}

void read_token(FILE *in, Token *token)
{
   int c;
   for(;;){
      c=fgetc(in);
      switch(c){
         case EOF:
            token->type=TOKEN_EOF;
            return;
         case '\n':
            token->type=TOKEN_END_OF_LINE;
            return;
         case '+': 
            token->type=TOKEN_PLUS;
            return;
         case '-':
            token->type=TOKEN_MINUS;
            return;
         case '*':
            token->type=TOKEN_MULTIPLY;
            return;
         case '/':
            token->type=TOKEN_DIVIDE;
            return;
         case '^':
            token->type=TOKEN_POWER;
            return;
         default:
            if(c>='0' && c<='9'){
               ungetc(c, in);
               token->type=TOKEN_INTEGER;
               read_integer(in, &token->value);
               return;
            }
            // otherwise do nothing - keep looping until get good input
      }
   }
}

// token stack =========================================

typedef struct TokenStack
{
   Token *stack;
   int size;
   int max_size;
} TokenStack;

void init_stack(TokenStack *s)
{
   s->stack=malloc(8*sizeof(Token));
   s->size=0;
   s->max_size=8;
}

int empty(TokenStack *s)
{
   return s->size==0;
}

int push(TokenStack *s, Token p)
{
   if(s->size==s->max_size){
      Token *snew=realloc(s,2*s->max_size*sizeof(Token));
      if(snew==0) return 0;
      s->stack=snew;
      s->max_size=2*s->max_size;
   }
   s->stack[s->size]=p;
   ++s->size;
   return 1;
}

Token top(TokenStack *s)
{
   assert(s->size>0);
   return s->stack[s->size-1];
}

Token pop(TokenStack *s)
{
   assert(s->size>0);
   --s->size;
   return s->stack[s->size];
}

void free_stack(TokenStack *s)
{
   free(s->stack);
   s->stack=0;
   s->size=0;
   s->max_size=0;
}

// evaluation ===============================================

long long int intpow(long long int base, long long int power)
{
   if(power<0){
      return 0;
   }else{
      long long int r=1, i;
      for(i=0; i<power; ++i) r*=base;
      return r;
   }
}

void eval_operator(TokenStack *R, TokenStack *P)
{
   Token c, r1, r2;
   assert(P->size>=1);
   c=pop(P);
   if(empty(R)) return;
   r2=pop(R); assert(r2.type==TOKEN_INTEGER);
   if(empty(R)) return;
   r1=pop(R); assert(r1.type==TOKEN_INTEGER);
   switch(c.type){
      case TOKEN_PLUS:
         //printf("evaluating "); print_token(&r1); printf("+"); print_token(&r2); printf("\n");
         push(R, int_token(r1.value+r2.value));
         break;
      case TOKEN_MINUS:
         //printf("evaluating "); print_token(&r1); printf("-"); print_token(&r2); printf("\n");
         push(R, int_token(r1.value-r2.value));
         break;
      case TOKEN_MULTIPLY:
         //printf("evaluating "); print_token(&r1); printf("*"); print_token(&r2); printf("\n");
         push(R, int_token(r1.value*r2.value));
         break;
      case TOKEN_DIVIDE:
         //printf("evaluating "); print_token(&r1); printf("/"); print_token(&r2); printf("\n");
         push(R, int_token(r1.value/r2.value));
         break;
      case TOKEN_POWER:
         //printf("evaluating "); print_token(&r1); printf("^"); print_token(&r2); printf("\n");
         push(R, int_token(intpow(r1.value, r2.value)));
         break;
      default:
         assert(0);
   }
}

// main =====================================================

int main()
{
   Token t;
   TokenStack R, P;
   init_stack(&R);
   init_stack(&P);

   for(;;){
      for(;;){
         read_token(stdin, &t);
         //printf("READ TOKEN: "); print_token(&t); printf("\n");
         switch(t.type){
            case TOKEN_PLUS:
            case TOKEN_MINUS:
            case TOKEN_MULTIPLY:
            case TOKEN_DIVIDE:
            case TOKEN_POWER:
               while(!empty(&P)){
                  if(precedence[t.type]<precedence[top(&P).type]
                  || (left_associative[t.type] && precedence[t.type]==precedence[top(&P).type])){
                     eval_operator(&R, &P);
                  }else
                     break;
               }
               //printf("pushing "); print_token(&t); printf(" on P\n");
               push(&P, t);
               break;
            case TOKEN_EOF:
            case TOKEN_END_OF_LINE:
               //printf("ending expression...\n");
               goto finish_expression;
               break;
            case TOKEN_INTEGER:
               //printf("pushing "); print_token(&t); printf(" on R\n");
               push(&R, t);
               break;
         }
      }
      finish_expression:
      //printf("finishing up: P.size=%d\n", P.size);
      while(!empty(&P)){
         eval_operator(&R, &P);
      }
      printf("result:");
      while(!empty(&R)){
         printf(" %lld", pop(&R).value);
      }
      printf("\n");
      if(t.type==TOKEN_EOF)
         break;
   }
   free_stack(&R);
   free_stack(&P);
   return 0;
}