http://www.nowamagic.net/librarys/veda/detail/2307

http://www.nowamagic.net/librarys/veda/detail/2306

/**

*code by lichmama from cnblogs.com

*@逆波兰表达式的C实现

*算术支持的运算模式：

*   四则运算；

*   操作数不得大于9；

*   中间数（即运算当中的临时变量）不得超过127

**/

#include <stdio.h>

#include <stdlib.h>

typedef struct __STACK__ {

    char op;

    struct __STACK__ *next;

}STACK, *PSTACK;

void init(PSTACK *);

void push(PSTACK *, char);

void pop(PSTACK *, char *);

void clear(PSTACK *);

void destroy(PSTACK *);

char getoplevel(char op){

    if(op=='+' || op=='-')

        return ;

    if(op=='*' || op=='/')

        return ;

    return ;

}

char calc(char *rpn){

    char *p=rpn;

    char e;

    int x, y;

    PSTACK pStack;

    init(&pStack);

    while(*p){

        if(<=*p && *p<=){

            push(&pStack, *p);

        }else {

            pop(&pStack, &e);x=e;

            pop(&pStack, &e);y=e;

            switch(*p){

                case '+':push(&pStack, y+x);break;

                case '-':push(&pStack, y-x);break;

                case '*':push(&pStack, y*x);break;

                case '/':push(&pStack, y/x);break;

            }

        }

        p++;

    }

    pop(&pStack, &e);

    free(pStack);pStack=NULL;

    return e;

}

int main(void){

    char e;

    char old_exp[]="(3-1)*3+8/2+(9*3/(2+1)+3*4/6)-2=";

    char rpn_exp[]="";

    char *p=old_exp;

    char *r=rpn_exp;

    PSTACK gStack;

    init(&gStack);

//

    while(*p!='\0' && *p!='='){

        if(''<=*p && *p<=''){

            *r++=(*p-'');

        }else if(*p=='('){

            push(&gStack, '(');

        }else if(*p==')'){

            for(;;){

                pop(&gStack, &e);

                if(e=='(')break;

                *r++=e;

            }

        }else if(*p=='+' || *p=='-' || *p=='*' || *p=='/'){

            if(getoplevel(gStack->op)<getoplevel(*p)){

                push(&gStack, *p);

            }else{

                for(;;){

                    pop(&gStack, &e);

                    if(getoplevel(e)<getoplevel(*p)){

                        if(e!='#')push(&gStack, e);

                        push(&gStack, *p);break;

                    }

                    *r++=e;

                }

            }

        }

        p++;

    }

    for(;;){

        pop(&gStack, &e);

        if(e=='#')break;

        *r++=e;

    }

    //printf("%s\n", rpn_exp);

    printf("%d\n", calc(rpn_exp));

//

    clear(&gStack);

    destroy(&gStack);

    return ;

}

void init(PSTACK *s){

    *s=(PSTACK)malloc(sizeof(STACK));

    (*s)->op='#';

    (*s)->next=NULL;

}

void push(PSTACK *s, char e){

    PSTACK p=(PSTACK)malloc(sizeof(STACK));

    p->op=e;

    p->next=*s;

    *s=p;

}

void pop(PSTACK *s, char *e){

    if((*s)->next){

        PSTACK p=(*s);

        *e=(*s)->op;

        *s=(*s)->next;

        free(p);

        p=NULL;

    }else *e='#';

}

void clear(PSTACK *s){

    PSTACK p;

    while((*s)->next){

        p=*s;

        *s=(*s)->next;

        free(p);

        p=NULL;

    }

}

void destroy(PSTACK *s){

    free(*s);

    *s=NULL;

}