主要是考察把中缀表达式换为后缀表达式
然后运用堆栈求值的运算
我可以提供一点思路——供参考
【将中缀表达式转化为后缀】
#include
#include
#include
typedef struct node
{
char data; int code; int pri;
struct node *link;
}NODE;
struct Tb1
{
char data; int code; int pri;
}opchTb1[]={{'*',1,4},{'/',2,4},{'+',3,2},{'-',4,2},{'(',5,5},{')',6,1},{'\0',7,0},{'#',-1,0}};
NODE *optop;
char num[200], *numtop;
char expStr[200];
void push(char x,int c,int p,NODE **toppt)
{
NODE *q=(NODE *)malloc(sizeof(NODE));
q->data=x;
q->code=c;
q->pri=p;
q->link=*toppt;
*toppt=q;
}
int pop(char *op,int *cp, NODE **toppt)
{
NODE *q=*toppt;
if(*toppt==NULL) return 1;
*op=q->data;
*cp=q->code;
*toppt=q->link;
free(q);
return 0;
}
int expr(char *pos)
{
struct Tb1 *op;
char sop;
int type,code,n,m,i,c;
optop=NULL;
numtop=num;
n=m=0;
c=' ';
push('#',0,0,*optop);
while(1){
while(c==' '||c=='\t') c=*pos++;
if(isalpha(c)){
*numtop++=' ';
while(isalpha(c)||isdigit(c)) {*numtop++=c;c=*pos++;}
if(m) return 1;
m=1;
continue;
}
else {
for(i=0;opchTb1[i].code!=-1&&opchTb1[i].data!=c;i++)
if(opchTb1[i].code==-1) return 3;
op=&opchTb1.[i];
type=opchTb1.[i].code;
c=*pos++;
}
if(type<5){
if(m!=1) return 1;
m=0;
}
if(type==5) n++;
if(type==6){
if(n--==0) return 2;
if(op->pri>optop->pri)
if(op->data=='(') push(op->code,1,*optop);
else push(op->data,op->code,op->pri,*optop);
else{
while(optop!=NULL&&op->pri<=optop->pri) {
pop(&sop,&code,&optop);
if(code<5&&code>0) {
*numtop++=' ';
*numtop++=sop;
}
}
if(op->data=='\0') return(n!=0||(m!=1&&numtop>num))?4:(*numtop='\0');
else if(op->data!=')') push(op->data,op->code,op->pri,&optop);