- /*
- 后缀表达式转为中缀表达式
- 问题描述:
- 将由数字和四则运算符组成的后缀表达式变换为中缀表达式,输入的后缀表达式
- 的运算符不超过15个,要求转换后的中缀表达式中不出现不必要的括号。例如,整个
- 表达式的括号要省略,不影响计算顺序括号要省略。
- 输入形式:
- 程序从标准输入读入一行字符串,是一个合法的后缀表达式,数字和运算符之间
- 由空格分隔。数字可以是带小数部分的浮点数。
- 输出形式:
- 向标准输出打印结果,输出只有一行,是转换后的中缀表达式。
- 并且 :
- 1、各分量(包括括号)紧密输出,不使用空格进行分隔;
- 2、在转换后的各运算数的出现顺序不变;
- 3、浮点数保留输入时的小数位数。
- */
- #include<stdio.h>
- #include<stdlib.h>
- struct Expression;
- typedef struct Expression *Node;
- struct Expressionlist;
- typedef struct Expressionlist *Elist;
- struct Expression //结点,包含一个符号信息和next指针
- {
- char c;
- Node next;
- };
- struct Expressionlist //表达式指针数组
- {
- int size;
- Node *Lists;
- };
- int node_position=0; //定义全局变量
- Elist InitiaExpressionList(int s) //初始化,注意此处函数返回的是指针
- {
- Elist E; //声明一个表达式指针数组
- int i;
- E=malloc(sizeof(struct Expressionlist)); //开辟空间
- E->size=s;
- E->Lists=malloc( sizeof(Node) * E->size ); //开辟空间存储size个结点,分配Lists数组的空间
- for(i=0 ; i < E->size ; i++)
- {
- E->Lists[i]=malloc(sizeof(struct Expression)); //分配空间,然后把Lists数组的指针指向这个空间
- E->Lists[i]->next=NULL;
- }
- return E;
- }
- int FindEmptyNode(Elist E) //在结点数组中,找到为空的结点
- {
- int i;
- for( i=0 ; i < E->size ; i++ )
- if( E->Lists[i]->next == NULL )
- return i;
- return -1;
- }
- void CreateNode(Elist E,int flag,char ch) //在指针数组的指定位置的末尾添加结点信息
- {
- Node newNode,p;
- p=E->Lists[flag];
- p->c='*'; //当该链表中只有一个数时把该链表的运算符定义为*(或/)
- while(p->next!=NULL)
- p=p->next;
- newNode=malloc(sizeof(struct Expression));
- newNode->c=ch;
- newNode->next=p->next;
- p->next=newNode;
- }
- void EmptyNode(Elist E,int flag) //重置结点为空
- {
- Node p,r;
- E->Lists[flag]->c='+';
- p=E->Lists[flag]->next;
- while(p!=NULL)
- {
- r=p;
- p=p->next; //r作为p的前一个结点
- E->Lists[flag]->next=p;
- free(r);
- }
- free(p);
- }
- void PrintNode(Node n) //输出链表信息
- {
- Node p; //定义指针表示输出的结点
- p=n->next; //若代码是p=L; 会输出L里面的废信息,p=L->next跳过头指针的废信息
- if(p==NULL) //若p一开始就为空,即L->next = NULL,此时链表为空
- {
- printf("空\\n");
- exit(0);
- }
- else
- {
- while(1) //一直循环输出,直到p为空
- {
- if(p==NULL)
- break;
- printf("%c",p->c);
- p=p->next;
- }
- }
- }
- void ConnectNode(Elist E,int flag,char ch) //连接两个链表
- {
- Node p,q,f;
- if(flag==0)
- {
- printf("错误\\n");
- exit(0);
- }
- E->Lists[flag-1]->c=ch;
- p=E->Lists[flag-1];
- f=E->Lists[flag]->next;
- while(p->next!=NULL)
- p=p->next;
- q=malloc(sizeof(struct Expression));
- q->c=ch;
- q->next=p->next;
- p->next=q;
- p=q;
- //此处连接两个链表应该把第二个链表内全部结点的信息复制到第一个链表中,而不是仅仅是把第一个
- //链表的尾结点指向第二个链表的头结点,因为第二个链表会执行清空操作
- while(f!=NULL)
- {
- q=malloc(sizeof(struct Expression));
- q->c=f->c;
- q->next=p->next;
- p->next=q;
- p=q;
- f=f->next;
- }
- EmptyNode(E,flag); //第二个链表执行清空操作
- node_position--;
- }
- void BracketNode(Elist E,int flag) //在结点数组的指定位置的首尾添加括号
- {
- Node begin,end,p; //p作为标记结点,标志链表尾结点
- begin=malloc(sizeof(struct Expression)); //在链表头部插入左括号符'('
- begin->c='(';
- begin->next=E->Lists[flag]->next;
- E->Lists[flag]->next=begin;
- p=E->Lists[flag];
- while(p->next!=NULL)
- p=p->next;
- end=malloc(sizeof(struct Expression)); //在链表尾部插入右括号符')'
- end->c=')';
- p->next=end;
- end->next=NULL;
- }
- void main()
- {
- Elist E;
- int i;
- char str[80]; //存储输入的后缀表达式
- int space_flag=0; //当前字符是否是空格的标记
- E=InitiaExpressionList(10); //初始化
- gets(str); //从键盘读入后缀表达式的字符串
- for(i=0;str[i]!='\\0';i++)
- {
- if( (str[i]>='0' && str[i]<='9') || str[i]=='.' )
- {
- if( space_flag==1 ) //上一个字符是空白字符,将读入的字符存入新链表
- {
- node_position++;
- CreateNode( E , node_position , str[i] );
- }
- else //否则存入当前链表
- CreateNode( E , node_position , str[i] );
- space_flag=0;
- }
- else if( str[i]==' ' ) //当前字符是空白字符跳过本次循环
- {
- space_flag=1;
- continue;
- }
- else if( str[i]=='+' || str[i]=='-' ) //读入+或-运算符把两个链表连接成一个
- {
- space_flag=0;
- ConnectNode( E , node_position , str[i] );
- }
- else if( str[i]=='*' || str[i]=='/') //读入* /运算符
- {
- space_flag=0;
- //判断两个链表的符号,如果优先级低的话在该链表两端加上括号
- if( E->Lists[node_position]->c=='+' || E->Lists[node_position]->c=='-' )
- BracketNode( E , node_position );
- if( E->Lists[node_position-1]->c=='+' || E->Lists[node_position-1]->c=='-' )
- BracketNode( E, node_position-1 );
- ConnectNode( E , node_position , str[i] ); //连接两个链表
- }
- }
- PrintNode(E->Lists[0]); //输入最后的表达式
- printf("\\n");
- }
- //该片段来自于http://www.codesnippet.cn/detail/160920135937.html
来源: http://www.codesnippet.cn/detail/160920135937.html