postfix notation 後序演算

之前學到的, 做個筆記 後序演算


 1+2*2+(3/(5+4))
人類習慣看此種表示方法 中序(infix)
要處括弧 (parenthesis) 和 operator 的優先權 (precedence) 實在是很麻煩

所以才要有此 postfix 這種表示方法,
它為電腦去除了 優先權, 及括弧的問題
因此, 電腦在計算一個expression時
方法是這樣：
所有的 infix 先轉成 postfix
1 2 2 * 3 5 4 + / + +
並且把資料存起來

接者把postfix的東西push到 stack裡
如果是數字 直接push
如果是運算子 從stack pop出兩個數字, 運算完再push回去

至於要中序怎麼轉後序呢
如果是運算元 (operand), 存進postfix_array
如果是個運算子 (operator), 將它先push到 op_stack
遇到下個運算子時, 將op_stack裡優先權比它大的全部pop出來存到postfix_array裡

為了解決括弧的優先問題
優先權設為兩種
一種是在stack裡的
另一種是coming的
左括弧 為coming時, 其優先權最大, 因此在op_stack裡的運算子沒有一個能pop出來
左括弧在op_stack時, 其優先權最小, 因此它不會因為coming的運算子比他小,  而被pop出來
code

typedef enum {end,add,sub,mul,div,mod,lp,rp,not} Operator;

struct stack{
    Operator op[OP_MAX];
    long data[OP_MAX];
};

double eval_postfix(struct stack *post)
{
    int i = 0, top = -1;
    double eval[OP_MAX];
    Operator op;
    while(post->op[i]!=end){
        if(post->op[i]!=not){
            op = post->op[i];
            if(op==add)
                eval[top-1]
                   = eval[top-1]+eval[top];
            if(op==sub)
                eval[top-1]
                   = eval[top-1]-eval[top];
            if(op==mul)
                eval[top-1]
                   = eval[top-1]*eval[top];
            if(op==div)
                eval[top-1]
                   = eval[top-1]/eval[top];
            top--;
        }
        else
            eval[++(top)] = post->data[i];
        i++;
    }
    return eval[top];
}

void in_to_post(const char *expr,struct stack *s)
{
    Operator op,ops[OP_MAX];
    int i = 0, optop = 0, stop = -1,isf = 0;
    double t = 0,frac = 0;
    int icp[ ] = {0,2,2,3,3,3,9},
        isp[ ] = {0,2,2,3,3,3,1};
    ops[optop] = end;
    while(expr[i]){
        if(expr[i]>='0'&&expr[i]<='9'){
            t = expr[i++]-'0';
            while(expr[i]>='0'&&expr[i]<='9'){
                t *= 10.0;
                t += expr[i++]-'0';
            }
            if(expr[i]=='.'){
                i++;
                while(expr[i]>='0'&&expr[i]<='9'){
                    frac /= 10.0;
                    frac += expr[i++]-'0';
                }
            }
            s->data[++stop] = t+frac;
            s->op[stop] = not;
        }
        if(!expr[i]) break;
        switch(expr[i]){
            case '+': op = add;break;
            case '-': op = sub;break;
            case '*': op = mul;break;
            case '/': op = div;break;
            case '%': op = mod;break;
            case '(': op =  lp;break;
            case ')': op =  rp;break;
        }
        if(op==rp){
            while(ops[optop]!=lp)
                s->op[++stop] = ops[optop--];
            optop--;//remove left parenthesis
        }
        else{
            while(isp[ops[optop]]>=icp[op])
            //have '=': a+b+c => ab+c+, don't have => abc++
                s->op[++stop] = ops[optop--];
            ops[++optop] = op;
        }
        i++;
    }
    while(ops[optop]!=end)
        s->op[++stop] = ops[optop--];
    s->op[++stop] = end;
}