简单实现了下,不是太严谨,大致逻辑就是这样的
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) |