中缀表达式转后缀表达式以及后缀表达式的实现

简单实现了下，不是太严谨，大致逻辑就是这样的

suffix函数：后缀表达式的实现

infixtosuffix函数：中缀表达式转后缀表达式

前面几个函数是栈的实现

后缀表达式的实现关键是利用栈

左括号在栈内是优先级最小的，在外面优先级则是最大的,isp表示栈内符号的优先级，osp表示栈外符号的优先级，比如左括号的枚举值为LPRAM，则isp[LPRAM] = 0 小于其他符号的优先级，osp[LPRAM]大于其他符号的优先级

 

/*
 * 2008/06/20 By Yao Jianming
 */
#include
#include
#include

typedef enum {LPRAM=0, RPRAM, MUL, DIV, MOD, ADD, SUB, NUM, EOS} predre;
int isp[] = {0, 19, 18, 17, 16, 15, 14};
int osp[] = {20, 19, 18, 17, 16, 15, 14};

#define maxsize 1000
struct seqstack {
    int *data;
    int top;
    int stacksize;
};

void initstack(seqstack *s)
{
    s->data = (int*)malloc(maxsize*sizeof(int));
    s->top = -1;
    s->stacksize = maxsize;
}

void pushstack(seqstack *s, int value)
{
    assert(s->top < s->stacksize);
    s->data[++s->top] = value;
}

int popstack(seqstack *s)
{
    assert(s->top > -1);
    return s->data[s->top--];
}

int gettop(seqstack *s)
{
    assert(s->top > -1);
    return s->data[s->top];
}

bool isempty(seqstack *s)
{
    if(s->top == -1)
        return true;
    else
        return false;
}

predre get_token(char ch)
{
    switch(ch) {
    case '+':   return ADD;
    case '-':   return SUB;
    case '*':   return MUL;
    case '/':   return DIV;
    case '%':   return MOD;
    case '(':   return LPRAM;
    case ')':   return RPRAM;
    case '\0':  return EOS;
    default:    return NUM;
    }
}

int suffix(char *haystack)
{
    seqstack s;
    initstack(&s);
    char *p = haystack;
    predre ret = get_token(*p);
    while (ret != EOS) {
        if(ret == NUM) {
            pushstack(&s, *p-'0');
        } else {
            int p1 = popstack(&s);
            int p2 = popstack(&s);
            switch(ret) {
            case ADD: pushstack(&s, p1+p2); break;
            case SUB: pushstack(&s, p1-p2); break;
            case MUL: pushstack(&s, p1*p2); break;
            case DIV: pushstack(&s, p1/p2); break;
            case MOD: pushstack(&s, p1%p2); break;
            }
        }
        ret = get_token(*(++p));
    }
    return popstack(&s);
}

void infixtosuffix(char *from, char *to)
{
    seqstack s;
    initstack(&s);
    int i=0;
    char *p = from;
    predre ret = get_token(*p);
    while(ret != EOS) {
        if(ret == NUM) {
            to[i++] = *p;
        } else if(ret == RPRAM) {
            while(1) {
                char ch = (char)popstack(&s);
                if(ch == '(') break;
                to[i++] = ch;
            }
        } else {
            if(isempty(&s) == true) {
                pushstack(&s, *p);
            } else {
                predre in = get_token((char)gettop(&s));
                if(osp[ret] < isp[in]) {
                    to[i++] = (char)popstack(&s);
                }
                pushstack(&s, *p);
            }
        }
        ret = get_token(*(++p));
    }
    while(1) {
        if(isempty(&s) == true)
            break;
        to[i++] = (char)popstack(&s);
    }
}

int main()
{
    char *p = "2*(3+4)";
    char q[1024] = {0};
    infixtosuffix(p, q);
    printf("q = %s\n", q);
    int ret = suffix(q);
    printf("ret:%d\n", ret);
    return 0;
}