后缀表达式算法:用栈对后缀表达式求值的算法

on 2009-2-12 in C 教程 | 0 Comment


第种

/* 此功能是求出用户输入整形表达式值*/
/*输入表达式请用#结尾比如:2+3+5应输入:2+3+5#*/
# <stdio.h>
# MAXSIZE 16

typedef struct{
data[MAXSIZE];
top;
base;
}seqstack; /* 顺序栈定义*/
/*以下为声明*/
void InitStack(seqstack *);
Empty(seqstack *);
void Push(seqstack *, );
Pop(seqstack *);
GetTop(seqstack *);
Operate( ,char , );
char Proceed(char ,char );
In(char );
EvalExpres(void);

/* 定义两个栈分别存放运算符和操作数*/
seqstack StackR,StackD;

/*主*/

{
v;
char ch;
while(1)
{
prf("end with #,for example 2+3+5 input:2+3+5#\n");
prf("calculate:") ;
v = EvalExpres;
prf("The result is:%d",v);
/*以下为控制*/
prf("\nInput 'q' to quit and ENTER run again:");
do{
scanf("%c",&ch);
(ch 'q' || ch 'Q')
exit(0);
}while(ch!='\n');
system("cls");
}
0;
}

void InitStack(seqstack *s)
{ s->top = 0;
s->base = 0;
} /* 化栈*/


Empty(seqstack *s)
{ (s->top s->base)
1;

0;
} /* 判断栈是否为空*/


void Push(seqstack *s, x)
{
(s->top MAXSIZE)
{ prf("OVER FLOW!\n");
exit(0);
}

{ s->data[s->top] = x;
s->top;
}
} /* 进栈 */

Pop(seqstack *s)
{ e;
(Empty(s))
{ prf("Under flow!\n");
0;
} /* 下溢*/

{ s->top--;
e = s->data[s->top];
e;
}
} /* 出栈*/

GetTop(seqstack *s) /*取栈顶元素*/
{
(Empty(s))
{ prf("Under flow!\n");
0;
}

s->data[s->top-1];
}

EvalExpres(void) /* 表达式求解*/
{
a,b,i=0,s=0;
char c[80],r;
InitStack(&StackR);
Push(&StackR,'#');
InitStack(&StackD);
prf(" end with #");
gets(c);
while(c[i]!='#' || GetTop(&StackR)!='#')
{
(!In(c[i])) /* 判断读入不是运算符 是则进栈*/
{ (c[i] >= '0' && c[i] <= '9')
{
s c[i]-'0';
while(!In(c[i])) /*此处实现功能为当输入数字为多位数时*/
{ s*=10;
s c[i]-'0';
}
Push(&StackD,s+'0');
s = 0;
}

{
prf("wrong!\n");
0;
}
}

switch(Proceed(GetTop(&StackR),c[i])) /* 此用来比较读取运算符和栈顶运算符优先级*/
{
'<': /* 栈顶元素优先级高*/
Push(&StackR,c[i]);
i;
;
'=': /* 遇到匹配小括号时则去掉他*/
Pop(&StackR);
i;
;
'>': /* 栈顶优先级低则出栈并将结果写入栈内*/
r = Pop(&StackR);
a = Pop(&StackD)-'0';
b = Pop(&StackD)-'0';
Push(&StackD,Operate(a,r,b)) ;
;
}
}
(GetTop(&StackD)-'0'); /* 返回运算结果*/
}



In(char c) /*问题2:解决In问题:判断C是否为运算符是返回1否则返回0*/
{
char ch[7]={'+','-','*','/','#','(',')'};
i;
for(i = 0; i < 7; i)
(c ch[i])
1;

0;
}

char Proceed(char op,char c) /*op为栈顶元素c为当前读入运算符,比较 2者优先级*/
{ /*问题1:解决Proceed*/
char ch;
(op'(' && c')' || op'#' && c'#' )
ch = '=';

(op'+' || op'-') /*栈顶元素为‘+’或‘-’时候*/
switch(c)
{
'+':
'-':
')':
'#': ch = '>'; ;
'*':
'/':
'(': ch = '<';
}

(op'*' || op'/') /*栈顶元素为‘*’或‘/’时候*/
switch(c)
{
'+':
'-':
'*':
'/':
')':
'#': ch = '>'; ;
'(': ch = '<';
}

(op'(') /*栈顶元素为‘(’时候*/
switch(c)
{
'+':
'-':
'*':
'/':
'(': ch = '<'; ;
'#': prf("Error!\n"); exit(0);
}

(op')') /*栈顶元素为‘)’时候*/
switch(c)
{
'+':
'-':
'*':
'/':
'#': ch = '>'; ;
'(': prf("Error!\n"); exit(0);
}

(op'#') /*栈顶元素为‘#’时候*/
switch(c)
{
'+':


'-':
'*':
'/':
'(': ch = '<'; ;
')': prf("Error!\n"); exit(0);
}
ch;
}
/* 问题3:解决Operate*/
Operate( a,char r, b) /*返回由aRb值 */
{
s;
d1 = a;
d2 = b; /*把ab变为对应数字*/
switch(r)
{
'+': s = d1+d2; ;
'-': s = d2-d1; ;
'*': s = d1*d2; ;
'/': s = d2/d1;
}
(s+'0');
}


第 2种

# <stdio.h>
# <malloc.h>

# MaxSize 50

void trans(char *exp,char *postexp)
{
struct
{
char data[MaxSize];
top;
} op;
i=0;
op.top=-1;
while(*exp!='\0')
{
switch(*exp)
{
'(':
op.top;op.data[op.top]=*exp;
exp;;
')':
while(op.data[op.top]!='(')
{
postexp[i]=op.data[op.top];
op.top--;
}
op.top--;exp;;
'+':
'-':
while(op.top!=-1&&op.data[op.top]!='(')
{
postexp[i]=op.data[op.top];
op.top--;
}
op.top;op.data[op.top]=*exp;exp;;
'*':
'/':
while(op.data[op.top]'*'||op.data[op.top]'/')
{
postexp[i]=op.data[op.top];
op.top--;
}
op.top;op.data[op.top]=*exp;exp;;
' ':;
default:
while(*exp>='0'&&*exp<='9')
{
postexp[i]=*exp;
exp;
}
postexp[i]='#';
}
}
while(op.top!=-1)
{
postexp[i]=op.data[op.top];
op.top--;
}
postexp[i]='\0';
}

float compvalue(char *postexp)
{
struct
{
float data[MaxSize];
top;
} st;
float a,b,c,d;
st.top=-1;
while(*postexp!='\0')
{
switch(*postexp)
{
'+':
a=st.data[st.top];
st.top--;
b=st.data[st.top];
st.top--;
c=b+a;
st.top;
st.data[st.top]=c;
;
'-':
a=st.data[st.top];
st.top--;
b=st.data[st.top];
st.top--;
c=b-a;
st.top;
st.data[st.top]=c;
;
'*':
a=st.data[st.top];
st.top--;
b=st.data[st.top];
st.top--;
c=b*a;
st.top;
st.data[st.top]=c;
;
'/':
a=st.data[st.top];
st.top--;
b=st.data[st.top];
st.top--;
(a!=0)
{
c=b/a;
st.top;
st.data[st.top]=c;
}

{
prf("\n\t除零!\n");
exit(0);
}
;
default:
d=0;
while(*postexp>='0'&&*postexp<='9')
{
d=10*d+*postexp-'0';
postexp;
}
st.top;
st.data[st.top]=d;
;
}
postexp;
}
st.data[st.top];
}


{
char exp[MaxSize],postexp[MaxSize];
while(scanf("%s",&exp)!=EOF)
{
trans(exp,postexp);
prf("zhongzhuibiaodashi: %s\n",exp);
prf("houzuibiaodashi: %s\n",postexp);
prf("zhi: %g\n",compvalue(postexp));
}
0;
}


第 3种

#<stdio.h>
#<stdlib.h>
# add 43
# subs 45
# mult 42
# div 47
# MAXSIZE 100

typedef struct
{
data[MAXSIZE];
top;
}seqstack;
seqstack *s;

seqstack *Init /*栈化*/
{
seqstack *s;
s=(seqstack *)malloc((seqstack));
(!s)
{prf("FULL!");
NULL;
}

{s->top=-1;
s;
}
}


Empty(seqstack *s) /*栈空判断*/
{(s->top-1) 1;
0;
}

Push(seqstack *s, x) /*入栈*/
{(s->topMAXSIZE-1) 0;

{s->top;
s->data[s->top]=x;
1;
}
}

Pop(seqstack *s, *x) /*出栈算法*/
{ (Empty(s)) 0;

{*x=s->data[s->top];
s->top--;
1;
}
}


Top(seqstack *s) /*取栈顶元素*/
{(Empty(s)) 0;
s->data[s->top];
}

eval(char t, a1, a2)
{switch(t)
{ add:(a1+a2);
subs:(a1-a2);
mult:(a1*a2);
div:(a1/a2);
}
}

void
{char c;
op1,op2,temp,c1;
s=Init;
prf("Input:(end with #)\n");
while((c=getchar)!='#')
{(c'')continue;
(c>47&&c<58)
{putchar(c);
c1=c-48;
Push(s,c1);
}
(cadd||csubs||cmult||cdiv)


{putchar(c);
Pop(s,&op1);
Pop(s,&op2);
temp=eval(c,op2,op1);
Push(s,temp);
}
prf("It's wrong!\n");
}
Pop(s,&op1);
prf("=%d\n",op1);
getch;
}



第 4种

#<stdio.h>
#<stdlib.h>
# add 43
# subs 45
# mult 42
# div 47
# MAXSIZE 100

typedef struct
{
data[MAXSIZE];
top;
}STKzone;
typedef STKzone *STK;
typedef enum{ture=1,false=0} bool;
typedef enum{ok,error} status;
STKzone expSTKzone;
STK expSTK;

STK initSTK(STKzone *stkzone) /*栈化*/
{STK p;
p=stkzone;
p->top=0;
}

status push( *term,STK pstk) /*入栈*//*term前可以没有*同时将第28、71、81行稍作修改即可 */
{(pstk->topMAXSIZE) error;
pstk->data[pstk->top]=*term;
pstk->top;
ok;
}

bool emptySTK(STK pstk) /*栈空判断*/
{ (pstk->top0);
}

status pop( *pdata,STK pstk) /*出栈算法*/
{ (emptySTK(pstk)) error;
(pstk->top)--;
*pdata=pstk->data[pstk->top];
ok;
}


void synerror
{prf("\nyu fa cuo wu!");


}

eval(char tag, a1, a2)
{switch(tag)
{ add:(a1+a2);
subs:(a1-a2);
mult:(a1*a2);
div:(a1/a2);
}
}



{ char c;
op1,op2,temp,c1;
expSTK=initSTK(&expSTKzone);
prf("Input:\n");
while((c=getchar)!='\n')
{(c'')continue;
(c>47&&c<58)
{putchar(c);
c1=c-48;
(push(&c1,expSTK)error)
{prf("\n too long!\n");

}
}
(cadd||csubs||cmult||cdiv)
{putchar(c);
(pop(&op1,expSTK)error)synerror;
(pop(&op2,expSTK)error)synerror;
temp=eval(c,op2,op1);
push(&temp,expSTK);
}
synerror;
}
(pop(&op1,expSTK)error) synerror;
(!(emptySTK(expSTK))) synerror;
prf("=%d\n",op1);
getch;
}

第 5种

#<stdio.h>
#<stdlib.h>
# add 43
# subs 45
# mult 42
# div 47
# MAXSIZE 100

typedef struct
{
stkdata[MAXSIZE];
top;
}stack;

init_stack(stack *s)
{ s=(stack *)malloc((stack));
(!s)
{prf("FULL!\n");
0;
}

{s->top=-1;
1;
}
}

push(stack *s, x)
{ (s->topMAXSIZE-1)
{ prf("over flow\n");
0;
}

{s->top;
s->stkdata[s->top]=x;
1;
}
}

char pop(stack *s)

{ char e;
(s->top-1)
{
prf("under flow \n");
0;
}
e=s->stkdata[(s->top)--];
e;
}

void
{
stack *s1;
length,i,num1,num2,result,sum;
char s[100];
init_stack(s1);
prf("please input \n");
prf("warning:must less than 100\n");
gets(s);
length=strlen(s);
for(i=0;i<=length-1;i)
{ (s[i]>='1'&&s[i]<='9')
push(s1,s[i]-48);

{ num1=pop(s1);
num2=pop(s1);
switch(s[i])
{
add: {sum=num1+num2;
push(s1,sum);
;
}
subs:{sum=num2-num1;
push(s1,sum);
;
}
div:{sum=num2/num1;
push(s1,sum);
;
}

mult:{sum=num1*num2;
push(s1,sum);
;
}
}
}
}
result=s1->stkdata[s1->top];
prf("result is %d\n",result);
getch;
}
Tags:  后缀表达式算法

延伸阅读

最新评论

发表评论