C语言数据结构，下图第3题，选什么，为什么，谢谢
发布网友
发布时间：2022-04-20 09:07
共1个回答
热心网友
时间：2023-07-17 18:46
将四个选项的[后缀表达式]转为[中缀表达式]
选项 A. abcd*+-
后缀 cd* 转为中缀 c*d ,表达式展开为 ab(c*d)+-
后缀 b(c*d)+ 转为中缀 b+(c*d) ,表达式展开为 a(b+(c*d))-
后缀 a(b+(c*d))- 转为中缀 a-(b+(c*d)) ,中缀表达式就是 a-(b+c*d)
选项 B. abc+*d-
后缀 bc+ 转为中缀 b+c ,表达式展开为 a(b+c)*d-
后缀 a(b+c)* 转为中缀 a*(b+c) ,表达式展开为 (a*(b+c))d-
后缀 (a*(b+c))d- 转为中缀 (a*(b+c))-d ,中缀表达式就是 a*(b+c)-d [符合题目要求]
选项 C. abc*+d-
后缀 bc* 转为中缀 b*c ,表达式展开为 a(b*c)+d-
后缀 a(b*c)+ 转为中缀 a+(b*c) ,表达式展开为 (a+(b*c))d-
后缀 (a+(b*c))d- 转为中缀 (a+(b*c))-d ,去掉括号得中缀表达式 a+b*c-d
选项 D. -+*abcd
运算符都在操作数的前面,这是前缀表达式,不符合题目的要求.
所以,选项 B. abc+*d- 就是答案.
//C语言测试代码
//中缀表达式a-(b+c*d) 后缀表达式abcd*+- (这是选项A. abcd*+-)
//中缀表达式a*(b+c)-d 后缀表达式abc+*d- (这是选项B. abc+*d-)
//中缀表达式a+b*c-d 后缀表达式abc*+d- (这是选项C. abc*+d-)
//[中缀表达式]转换为[后缀表达式]
#include<stdio.h>
#include<stdlib.h>
struct stack_node
{
int data;
struct stack_node *next;
};
typedef struct stack_node stack_list;
typedef stack_list *link;
//检查链表是否是空
int empty(link stack)
{
return stack==NULL?1:0;
}
//对操作数进行运算
int get_value(int op,int operand1,int operand2)
{
int result;
switch(op)
{
case '*':
result=operand2*operand1;
break;
case '/':
result=operand2/operand1;
break;
case '+':
result=operand2+operand1;
break;
case '-':
result=operand2-operand1;
break;
default:
result=0;
break;
}
return result;
}
//检查是否是操作符
int isoperator(char oneChar)
{
int result=0;
switch(oneChar)
{
case '(':
case ')':
case '*':
case '/':
case '+':
case '-':
result=1;
break;
default:
result=0;
break;
}
return result;
}
//出栈
link pop(link stack,int *value)
{
link top;
if(empty(stack))
{
*value=0;
return NULL;
}
top=stack;
*value=top->data;
stack=top->next;
free(top);
return stack;
}
//计算[操作符]的优先级
int priority(char op)
{
int result=0;
switch(op)
{
case '*':
case '/':
result=3;
break;
case '+':
case '-':
result=2;
break;
case '(':
result=1;
break;
default:
result=0;
break;
}
return result;
}
//入栈
link push(link stack,int value)
{
link new_node;
new_node=(link)malloc(sizeof(stack_list));
if(!new_node)
{
return NULL;
}
new_node->data=value;
new_node->next=stack;
stack=new_node;
return stack;
}
int main()
{
link linkTotal=NULL;//[总栈]
link linkOperator=NULL;//[操作符栈]
char exp[]="a*(b+c)-d"; //中缀表达式a*(b+c)-d 后缀表达式abc+*d- (这是选项B. abc+*d-)
//char exp[]="a-(b+c*d)"; //中缀表达式a-(b+c*d) 后缀表达式abcd*+-
//char exp[]="a+b*c-d"; //中缀表达式a+b*c-d 后缀表达式abc*+d-
char oneChar;
int op=0;
int pos=0;
link linkResult=NULL;//[结果栈]
char *str=NULL;//后缀表达式的字符串
int len=0;//字符串的长度
int count=0;
//读取表达式的字符,入栈
oneChar=exp[pos];
while(oneChar!='\0')
{
//入栈前需要区分[操作符]和[操作数]
if(isoperator(oneChar))
{
//如果是右括号')',将右括号入[操作符栈]
if(oneChar=='(')
{
linkOperator=push(linkOperator,oneChar);
}
//如果是右括号')',就将[操作符栈]的[操作符]取出,放入[总栈],
//直至遇到其配对的左括号'("为止.
else if(oneChar==')')
{
while(!empty(linkOperator))
{
if(linkOperator->data=='(')
{
linkOperator=pop(linkOperator,&op);
break;
}
//取出[操作符],再放入[总栈]
linkOperator=pop(linkOperator,&op);
linkTotal=push(linkTotal,op);
}
}
else //如果不是右括号')',则按照常规操作
{
if(!empty(linkOperator))
{
while(!empty(linkOperator))
{
//检查操作符的优先级
if(priority(oneChar)>priority(linkOperator->data))
{
//[操作符]入[操作符栈]
linkOperator=push(linkOperator,oneChar);
break;
}
else
{
//取出栈顶的[操作符],再放入[总栈],然后在[操作符栈]里继续循环
linkOperator=pop(linkOperator,&op);
linkTotal=push(linkTotal,op);
}
}
if(empty(linkOperator))
{
//[操作符]入[操作符栈]
linkOperator=push(linkOperator,oneChar);
}
}
else
{
//[操作符]入[操作符栈]
linkOperator=push(linkOperator,oneChar);
}
}
}
else
{
//[操作数]入[总栈]
linkTotal=push(linkTotal,oneChar);
}
pos++;
oneChar=exp[pos];
}
//最后,检查[操作符栈]是否还有[操作符]
while(!empty(linkOperator))
{
//取出[操作符],再放入[总栈]
linkOperator=pop(linkOperator,&op);
linkTotal=push(linkTotal,op);
}
while(!empty(linkTotal))
{
linkTotal=pop(linkTotal,&op);
linkResult=push(linkResult,op);
len++;
}
str=(char*)malloc(len+1);
while(!empty(linkResult))
{
linkResult=pop(linkResult,&op);
str[count]=(char)op;
count++;
}
str[count]='\0';
printf("中缀表达式: %s\n",exp);
printf("后缀表达式: %s\n",str);
free(str);
printf("\n");
return 0;
}
