c语言实现中缀,后缀,前缀表达式转换并求值

c语言实现中缀,后缀,前缀表达式转换并求值九

#include<stdio.h> #include<stdlib.h> #define MAXNUM 100

typedef struct Node //定义存储中缀表达式的结点类型 {int data; int data1; char data2;

struct Node *next; }Lnode;

typedef struct Node2 //定义存储前缀表达式的结点类型 {int data; int data1; char data2;

struct Node2 *next; struct Node2 *prior; }Lnode2;

typedef int selemtype1; //定义运算数栈的结点

typedef struct //定义运算数栈的类型 {selemtype1 *base; selemtype1 *top; }sqstack1;

void InitStack1(sqstack1 &s) //新建一个空运算数栈 {s.base=(selemtype1 *)malloc(MAXNUM*sizeof(selemtype1)); s.top=s.base;

if(!s.base) printf("出错：申请空间失败！\\n"); }

void Push1(sqstack1 &s,selemtype1 &e) //运算数栈，入栈：插入元素e为新的栈顶元素

{ if(s.top-s.base>=MAXNUM)

printf("出错：表达式过长！1\\n"); *s.top++ =e; }

void GetTop1(sqstack1 s,selemtype1 &e) //运算数栈，用e返回栈顶元素

{e=*(s.top-1); }

void Popopnd1(sqstack1 &s,selemtype1 &e) //运算数栈，退栈：删除栈顶元素，并用e返回其值 {e=*--s.top; }

int stackempy1(sqstack1 s) //运算数栈，若为空栈返回1，否则返回0 {if(s.top==s.base) return 1; else return 0; }

typedef char selemtype2; //定义运算符栈的结点类型

typedef struct //定义运算符栈类型 {selemtype2 *base; selemtype2 *top; }sqstack2;

void InitStack2(sqstack2 &s) //新建一个空运算符栈 {s.base=(selemtype2 *)malloc(MAXNUM*sizeof(selemtype2)); s.top=s.base;

if(!s.base) printf("出错：申请空间失败！\\n"); }

void Push2(sqstack2 &s,selemtype2 &e) //运算符栈，入栈：插入元素e为新的栈顶元素

{ if(s.top-s.base>=MAXNUM)

printf("出错：表达式过长！2\\n"); *s.top++ =e; }

void GetTop2(sqstack2 s,selemtype2 &e) //运算符栈，用e返回栈顶元素 {e=*(s.top-1); }

void Popopnd2(sqstack2 &s,selemtype2 &e) //运算符栈，退栈：删除栈顶元素，并用e返回其值 {e=*--s.top; }

int stackempy2(sqstack2 s) //运算符栈，若为空栈返回1，否则返回0 {if(s.top==s.base) return 1; else return 0; }

void priority(char c,int &i) //确定运算符优先级 {if (c=='*'||c=='/'||c=='%') i=2 ; else if (c=='+'||c=='-') i=1 ; else i=0; }

int compare(char a,char b) //比较栈顶元素运算符与外部运算符优先级大小，外部优先级大则返回1，反之返回0 {int in,out; priority(a,in); priority(b,out);

if(out>in) return 1; else return 0; }

void Operat(sqstack1 &OPND,sqstack2 &OPTR) {int num1,num2,num; char c;

Popopnd1(OPND,num2); Popopnd1(OPND,num1); Popopnd2(OPTR,c); switch(c)

{case '+':num=num1+num2;break; case '-':num=num1-num2;break; case '*':num=num1*num2;break; case '/':num=num1/num2;break; case '%':num=num1%num2;break; }

Push1(OPND,

num); }

void Operatqianzhui(sqstack1 &OPND,sqstack2 &OPTR) {int num1,num2,num; char c;

Popopnd1(OPND,num1);

Popopnd1(OPND,num2); Popopnd2(OPTR,c); switch(c)

{case '+':num=num1+num2;break; case '-':num=num1-num2;break; case '*':num=num1*num2;break; case '/':num=num1/num2;break; case '%':num=num1%num2;break; }

Push1(OPND,num); }

void houzhuiqiuzhi(Lnode *p,int &e) {sqstack1 OPND; //运算数栈 sqstack2 OPTR; //运算符栈 int n; char c;

p=p->next; InitStack1(OPND); InitStack2(OPTR); while(p)

{switch(p->data) {case 1:n=p->data1; Push1(OPND,n); break;

case 2:c=p->data2; Push2(OPTR,c);

Operat(OPND,OPTR); break;

default:printf("结点有误"); break; }

p=p->next; }

Popopnd1(OPND,n); e=n; }

void zhongzhui(Lnode *p) {sqstack1 OPND; //运算数栈 sqstack2 OPTR; //运算符栈 int n;

//后缀表达式求值//中缀表达式求值 char c,c2; Lnode *first; first=p;

p=p->next; InitStack1(OPND); InitStack2(OPTR);

while(!stackempy2(OPTR)||p) {while(p)

{switch(p->data) {case 1:n=p->data1; Push1(OPND,n); break;

case 2:c=p->data2;

if(stackempy2(OPTR)) Push2(OPTR,c); else { switch(c)

{case '(': Push2(OPTR,c);break; case ')': GetTop2(OPTR,c2); while(c2!='(') {Operat(OPND,OPTR); GetTop2(OPTR,c2);} Popopnd2(OPTR,c2); break;

default: GetTop2(OPTR,c2);

if(compare(c2,c)) Push2(OPTR,c); else { Operat(OPND,OPTR); Push2(OPTR,c); }

break; } }

break;

default: printf("结点有误"); break; }

p=p->next; }

while(!stackempy2(OPTR)) Operat(OPND,OPTR); }

Popopnd1(OPND,n); p=first->next; while(p)

{if(p->data==1) printf("%d ",p->data1); if(p->data==2) printf("%c",p->data2);