复杂计算(带括号)含有中缀表达式转换

a.将中缀表达式计算转换成后缀表达式。

b. 后缀表达式的计算实现4.2.2中的算法，要考虑实际运算时，后缀表达式中相邻操作数的界定。

#include

#include

#include

#include

using namespace std;

#define max 100

typedef char elemtype;

typedef struct node

{

elemtype data;

struct node *next;

}listack;

void initstack(listack *&s)

{

s=(listack*)malloc(sizeof(listack));

s->next=NULL;

}

int stacklength(listack *s)

{

int i=0;

listack *p;

p=s->next;

while(p!=NULL)

{

i++;

p=p->next;

}

return i;

}

void clearstack(listack *s)

{

listack *p=s->next;

while(p!=NULL)

{

free(s);

s=p;

p=p->next;

}

}

{

return(s->next==NULL);

}

void push(listack *& s,elemtype e) {

listack *p;

p=(listack*)malloc(sizeof(listack)); p->data=e;

p->next=s->next;

s->next=p;

}

int pop(listack *&s,elemtype &e) {

listack *p;

if(s->next==NULL)

return 0;

p=s->next;

e=p->data;

s->next=p->next;

free(p);

return 1;

}

int gettop(listack *s,elemtype &e) {

if(s->next==NULL)

return 0;

e=s->next->data;

return 1;

}

void caculator(listack *&s)

{

if(stackempty(s))

return ;

listack *sq;

initstack(sq);

elemtype e,e1,e2;

e1=e2='0';

int sum=0;

while(!stackempty(s))

{

pop(s,e);

int i=e-'0';

if(i<=9&&i>=0)push(sq,e);

else

{

switch(e)

{

case'+':{

pop(sq,e1);

pop(sq,e2);

sum=(e2-'0')+(e1-'0');

e=sum+'0';

push(sq,e);

}

break;

case'-':{

pop(sq,e1);

pop(sq,e2);

sum=(e2-'0')-(e1-'0');

e=sum+'0';

push(sq,e);

}

break;

case'*':{

pop(sq,e1);

pop(sq,e2);

sum=(e2-'0')*(e1-'0');

e=sum+'0';

push(sq,e);

}

break;

case'/':{

pop(sq,e1);

pop(sq,e2);

if(e1-'0'==0){

printf("除表达式不是后缀表达式！/n");

return;

}

sum=(e2-'0')/(e1-'0');

e=sum+'0';

push(sq,e);

}

break;

}

}

}

printf("结果：");

int x=e-'0';

cout<}

int prinum(elemtype e)

{

int i=-1;

if(e=='+'||e=='-') i=0;

if(e=='*'||e=='/') i=1;

return i;

}

void main()

{

listack *s,*q,*p;

char t[max];

cout<<"输入表达式："<scanf("%s

elemtype e;

initstack(s);initstack(q);initstack(p);

int i=0;

while(t[i]!=0)

{

if(t[i]=='(') push(s,t[i]);

else if(t[i]==')')

{

while(!stackempty(s))

{

pop(s,e);

if(e=='(') break;

else

{

push(q,e);

printf("%c

}

}

if(e!='(')

{printf("输入有误！/n");

return;

}

}

else if(t[i]=='+'||t[i]=='-'||t[i]=='*'||t[i]=='/') {

if(stackempty(s)) push(s,t[i]);else

{

gettop(s,e);

int k=prinum(e);

int j=prinum(t[i]);

if(j>k)

push(s,t[i]);

else

{

pop(s,e);

printf("%c

push(q,e);

push(s,t[i]);

}

}

}

else {printf("%c

}

while(!stackempty(s))

{

pop(s,e);

push(q,e);

printf("%c

}

cout<while(!stackempty(q))

{

pop(q,e);

push(p,e);

}

caculator(p);

}