ACM 727 Equation

infix轉postfix。

讓我想到當年的作業了……
雖然當時要寫判斷合法、中序轉後續跟算值。
不過括號問題還傻傻的暴力解，兩個禮拜才把東西生出來，真是寫到快起肖。
用stack不就輕鬆多了嗎 -.-

結果現在1hr就完成中序轉後序，囧。

operand直接output，
operator要判斷優先度。
當吃進來的operator優先度比stack[top]優先度高，
就直接push；
低或相等的話，pop到stack[top]比operator高或stack為空為止。
所以(最高，直接丟到stack。
/、*次高，若top是*、/就要先pop，再push。
+、-最低，遇到其他+、-、*、/都要pop，再push。
遇到)要無條件pop到(為止。

(算是特例，吃進來時最高，但是在top時最低。
所以+、-、*、/遇到top為(時，就可以直接push。

最後當吃進來的token為'\0'時，pop到stack為空為止即可。
最後就是output格式問題。

/* ACM 727 Equation
 * mythnc
 * 2012/01/13 09:44:34
 * run time: 0.136
 */
#include <stdio.h>
#include <string.h>

#define LINEMAX  10
#define MAXSTACK 50

void postfix(void);
void pop(void);
void push(char *);

char stack[LINEMAX][MAXSTACK];
int count;

int main(void)
{
    scanf("%*d");
    getchar();
    getchar();
    postfix();

    return 0;
}

/* postfix: infix to postfix */
void postfix(void)
{
    char line[LINEMAX];

    count = 0;
    while (fgets(line, LINEMAX, stdin)) {
        line[strlen(line) - 1] = '\0';
        /* operator */
        if (line[0] == '+' || line[0] == '-' && strlen(line) == 1) {
            while (count > 0 && stack[count - 1][0] != '(')
                pop();
            push(line);
        }
        else if (line[0] == '*' || line[0] == '/') {
            while (count > 0 && stack[count - 1][0] != '('
                   && stack[count - 1][0] != '+' && stack[count - 1][0] != '-')
                pop();
            push(line);
        }
        else if (line[0] == '(')
            push(line);
        else if (line[0] == ')') {
            while (stack[count - 1][0] != '(')
                pop();
            count--;
        }
        /* terminal condition */
        else if (line[0] == '\0') {
            while (count != 0)
                pop();
            printf("\n\n");
        }
        /* operand */
        else
            printf("%s", line);
    }
    while (count != 0)
        pop();
    putchar('\n');
}

/* pop: print out the top element */
void pop(void)
{
    printf("%s", stack[--count]);
}

/* push: push line to stack */
void push(char *line)
{
    strcpy(stack[count++], line);
}