我的讲师给了我一个任务,让我创建一个使用 Stack 将中缀表达式转换为后缀的程序。我已经制作了堆栈类和一些函数来读取中缀表达式。
但是这个名为 inToPos(char string[]) 的函数负责使用堆栈将字符串 inFix 中的 inFix 表达式转换为字符串 postFix 中的 post fix 表达式,它正在创建一个断点。你们能帮助我并告诉我我做错了什么吗?
这些是我的代码,非常需要你的帮助.. :)
#include<stdio.h>
#include<stdlib.h>
#define MAX 15
#define true 1
#define false 0
typedef struct node* nodeptr;
typedef struct node{
int data;
nodeptr next;
}Node;
typedef struct{
int count;
nodeptr top;
}Stack;
typedef Stack* StackList;
StackList create();
void display(StackList list);
int isEmpty(StackList list);
void push(StackList list, int item);
void pop(StackList list);
int inToPos(char string[]);
int isOperator(char string[], int i);
int precedence(char x);
StackList create(){
StackList list;
list=(StackList)malloc(sizeof(Stack));
list->count=0;
list->top=NULL;
return list;
}
void display(StackList list){
nodeptr ptr;
ptr=list->top;
while(ptr!=NULL){
printf("%d ",ptr->data);
ptr=ptr->next;
}
printf("\n");
}
int isEmpty(StackList list){
return list->count==0;
//return list->top==NULL;
}
void push(StackList list, int item){
nodeptr temp;
temp=(nodeptr)malloc(sizeof(Node));
temp->data=item;
temp->next=list->top;
list->top=temp;
(list->count)++;
}
void pop(StackList list){
nodeptr temp;
temp=list->top;
list->top=temp->next;
temp->next=NULL;
free(temp);
(list->count)--;
}
int inToPos(char string[]){
int i,a=0;
char postfix[MAX];
StackList list=create();
for(i=0;string[i]!='\0';i++){
if(!isOperator(string,i)){
postfix[a]=string[i];
a++;
}
else if(isEmpty(list))
push(list,string[i]);
else{
if(precedence(string[i])>precedence(list->top->data))
push(list,string[i]);
else{
postfix[a]=list->top->data;
a++;
pop(list);
if(!isEmpty(list)){
while(precedence(list->top->data)<=precedence(string[i])){
postfix[a]=list->top->data;
a++;
pop(list);
}
}
else
push(list,string[i]);
}
}
}
puts(postfix);
}
int isOperator(char string[], int i){
switch(string[i])
{
case '+':
case '-':
case '*':
case '%':
case '/': return true;
default: return false;
}
}
int precedence(char x){
switch(x)
{
case '%':
case '*':
case '/': return 2;
case '+':
case '-': return 1;
default: return 0;
}
}
int main(void){
char string[MAX]="a+b*c-d";
inToPos(string);
}
请注意,inToPos 函数是使用以下算法生成的:
- 从左到右扫描中缀字符串。
- 初始化一个空栈。
- 如果扫描的字符是操作数,则将其添加到 Postfix 字符串。如果扫描的字符是运算符并且堆栈为空,则将字符推入堆栈。
- 如果扫描到的字符是运算符且堆栈不为空,则将字符的优先级与堆栈顶部的元素(topStack)进行比较。如果 topStack 的优先级高于扫描的字符,则弹出堆栈,否则将扫描的字符推入堆栈。只要 stack 不为空并且 topStack 优先于字符,就重复此步骤。重复此步骤,直到字符被扫描。
- (扫描完所有字符后,我们必须将堆栈可能包含的任何字符添加到 Postfix 字符串。)如果堆栈不为空,则将 topStack 添加到 Postfix 字符串并弹出堆栈。只要堆栈不为空,就重复此步骤。
- 返回后缀字符串。