基于中缀表达式的计算器.keywords: inorder tree变后缀; enum 类型与宏定义

calculator.c

/*
 * =========================================================
 *       Filename:  calculator.c
 *    Description:  deal with expression like this (4+2)*5-6/(2+1)
 *    number , + - * / , ()
 *    1.convert in-order to post-order
 *    2.you know how to compute post-order expr
 *
 * =========================================================
 */
#include <stdio.h>
#include <string.h>
#define SIZE 20
enum opclass{ /* specify operator class enum type auto assignment*/
    OPERATOR,
    NUMBER,
    LPAREN,
    RPAREN

};
/*---------------------------------------------------
 *  1.convert in-order to post-order
 *  we need a stack and queue
 *---------------------------------------------------*/
typedef struct stack Stack;
typedef struct queue Queue;
struct stack{
    char *operator[SIZE];
    int top;
};
struct queue{
    char *operand[SIZE];
    int head,tail;
};
void push(Stack *s,char *c);
char *pop(Stack *s);
int empty(Stack *s);
void inque(Queue *q,char *c);
char *deque(Queue *q);
void printq(Queue *q);
/*---------------------------------------------------
 *  classify op  and get precedence of operator
 *---------------------------------------------------*/
int classify(char *op);
int precedence(char *op);

/*---------------------------------------------------
 *  convert in-order to post-order
 *---------------------------------------------------*/
void convert(char *inorder[],int len,Queue *q);

int main(int argc,char *argv[]){
    Queue q;
    q.head=q.tail=0;

    convert(++argv,argc-1,&q);
    return 0;
}
void push(Stack *s,char *c){
    if(s->top==SIZE)
        printf("stack full\n");
    else{
        s->operator[s->top++]=c;
    }
}
char *pop(Stack *s){
    if(s->top==0){
        printf("stack empty\n");
        return NULL;
    }
    else
        return s->operator[--s->top];
}
int empty(Stack *s){
    return (s->top==0)?1:0;
}
void inque(Queue *q,char *c){
    if(q->tail==SIZE)
        printf("queue full\n");
    else
        q->operand[q->tail++]=c;
}
char *deque(Queue *q){
    if(q->head==q->tail){
        printf("empty queue\n");
        return NULL;
    }
    else
        return q->operand[q->head--];
}
void printq(Queue *q){
    int iter;
    for(iter=q->head;iter<q->tail;iter++)
        printf("%s%s",q->operand[iter],(iter==q->tail-1)?"\n":" ");
}
int classify(char *op){
    char first=*op;
    if(first=='+' || first=='-' || first=='x' || first=='/')
        return OPERATOR;
    else if(first>='0' && first<='9')
        return NUMBER;
    else if(first=='(')
        return LPAREN;
    else
        return RPAREN;
}
int precedence(char *op){
    char c=*op;
    if(c=='+' || c=='-')
        return 1;
    else
        return 2;
}

void convert(char *inorder[],int len,Queue *q){
    int iter;
    int class;// specify the class of op

    Stack opstack; /* initialize operator stack */
    opstack.top=0;
    Stack *stack=&opstack;
    char *top;// the top op in operator stack
    for(iter=0;iter<len;iter++){
        class=classify(inorder[iter]);
        if(class==NUMBER) {/* 如果是数字 直接入队 */
            inque(q,inorder[iter]);
//            printf("%s\n","ok");
        }
        else if(class==OPERATOR){ /* 如果是运算符 则保证栈顶运算符优先级<当前运算符 基础上压栈 */
            while(!empty(stack)){
                top=stack->operator[stack->top-1];
                if(classify(top)==OPERATOR && precedence(top)>=precedence(inorder[iter]))
                    inque(q,pop(stack));
                else
                    break;
            }
            push(stack,inorder[iter]);
//            printf("%s\n","push");
        }
        else if(class==LPAREN) /* 如果是左括 直接压栈 */
            push(stack,inorder[iter]);
        else{ /* 如果是右括 将与之匹配的左括之间的运算符出栈 并入队 */
            while(!empty(stack) && classify(top=stack->operator[stack->top-1])!=LPAREN)
                inque(q,pop(stack));
            if(!empty(stack))
                pop(stack);
        }
    }
    while(!empty(stack)){
        inque(q,pop(stack));
    }
    printq(q);
}

中缀转后缀
http://zh.wikipedia.org/wiki/%E8%B0%83%E5%BA%A6%E5%9C%BA%E7%AE%97%E6%B3%95