Chinaunix首页 | 论坛 | 博客
  • 博客访问: 208316
  • 博文数量: 35
  • 博客积分: 2691
  • 博客等级: 少校
  • 技术积分: 527
  • 用 户 组: 普通用户
  • 注册时间: 2008-01-11 09:42
文章分类

全部博文(35)

文章存档

2012年(5)

2010年(6)

2009年(2)

2008年(22)

我的朋友

分类: C/C++

2008-06-20 14:24:13

简单实现了下,不是太严谨,大致逻辑就是这样的
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;
}
阅读(1939) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~