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

enum TOKEN {BOTTOM, PLUS, MINUS, MUL, DIV, POW, UNARYMINUS, LPAREN, RPAREN, ID};
enum BOOL {FALSE, TRUE};

int prec_table[][10] = {
              /* _    +    -    *    /    ^    -    (    )   ID */
    /* _ */ {   '!', '>', '>', '>', '>', '>', '>', '>', '!', '>'},
    /* + */ {   '!', '<', '<', '<', '<', '>', '>', '>', '=', '>'},
    /* - */ {   '!', '>', '>', '<', '<', '>', '>', '>', '=', '>'},
    /* * */ {   '!', '<', '<', '>', '>', '<', '>', '>', '=', '>'},
    /* / */ {   '!', '<', '<', '>', '>', '<', '>', '>', '=', '>'},
    /* ^ */ {   '!', '<', '<', '<', '<', '<', '>', '>', '=', '>'},
    /* - */ {   '!', '>', '>', '>', '>', '>', '>', '>', '=', '<'},
    /* ( */ {   '!', '>', '>', '>', '>', '>', '>', '>', '=', '>'},
    /* ) */ {   '!', '!', '!', '!', '!', '!', '!', '!', '!', '!'},
    /* ID */{   '!', '<', '<', '<', '<', '<', '<', '<', '=', '!'},
};

int op_stack[256];
int sp = -1; /* bottom - 1*/
int can_unary = FALSE;

int
gettoken()
{
    static i = 0;
    static char tokens[] = {'-', '(', 'a', '+', 'b', '+', 'c', ')', 0};
    int token;

    token = tokens[i++];

    if (i==1 || strchr("(-+*^/", tokens[i-2])) {
        can_unary = TRUE;
    }
    else {
        can_unary = FALSE;
    }

    return token;
}
int
get_token_num(int token)
{
    int token_num;

    switch (token) {
      case '+':
        token_num = 1;
        break;
      case '-':
        if (can_unary)
            token_num = UNARYMINUS;
        else
            token_num = 2; /* binary minus */
        break;
      case '*':
        token_num = 3;
        break;
      case '/':
        token_num = 4;
        break;
      case '^':
        token_num = 5;
        break;
      case '(':
        token_num = 7;
        break;
      case ')':
        token_num = 8;
        break;
      case '@':
        token_num = UNARYMINUS;
        break;
      case 0:
        token_num = 0;
        break;
      default:
        token_num = ID;
        break;
    }

    can_unary = FALSE;
    return token_num;
}

int
parse()
{
    int token;
    int token_num;
    int prec;

    while (token = gettoken()) {
#if DEBUG
        printf("\ntoken = '%c'\n", token);
#endif
        token_num = get_token_num(token);
        prec = prec_table[get_token_num(op_stack[sp])][token_num];
#if DEBUG
        printf("op_stack[sp]:'%c', %d, token_num:%d, '%c'\n",
               op_stack[sp], get_token_num(op_stack[sp]), token_num, prec);
#endif
        if (prec == '>') {
            if (token_num == UNARYMINUS)
                op_stack[++sp] = '@'; /* unary minus */
            else
                op_stack[++sp] = token;
        }
        else if (prec == '<') {
            if (op_stack[sp] == '@' && token_num == ID) {
                printf("%c ", token); /* put ID */
            }

            while (prec == '<') {
                printf("%c ", op_stack[sp--]);
                prec =  prec_table[get_token_num(op_stack[sp])][token_num];
#if DEBUG
        printf("op_stack[sp]:'%c', %d, token_num:%d, '%c'\n",
               op_stack[sp], get_token_num(op_stack[sp]), token_num, prec);
#endif
            }

            if (token_num == UNARYMINUS) {
                op_stack[++sp] = '@';
            }
            else if (token_num == ID) {
                continue;
            }
            else {
                op_stack[++sp] = token;
            }

        }
        else if (prec == '=') {
            while (op_stack[sp] != '(') {
                 printf("%c ", op_stack[sp--]);
            }
            sp--; /* drop '(' */
        }
        else if (prec == '!')
            fprintf(stderr, "parsing error:\n");
        else
            fprintf(stderr, "can't happen token=%c\n", token);
    }

    //printf("sp = %d\n", sp);
    if (sp != 0) {
        while (sp >= 0) {
            int op = op_stack[sp];
            if (op != '(' && op != ')')
                printf("%c ", op);
            sp--;
        }
    }

    return 0;
}

int
main()
{
    op_stack[++sp] = 0;
    parse();
    return 0;
}