使用堆栈中缀到 Postfix [英] Infix to Postfix using stack
问题描述
我的讲师给了我一项作业,让我创建一个程序,使用 Stack 将中缀表达式转换为后缀.我已经制作了堆栈类和一些函数来读取中缀表达式.
My lecturer gave me an assignment to create a program to convert an infix expression to postfix using Stack. I've made the stack classes and some functions to read the infix expression.
但是这个名为 inToPos(char string[]) 的函数正在创建一个断点,它负责将字符串 inFix 中的 inFix 表达式转换为字符串 postFix 中的后修复表达式.你们能帮我一下,告诉我我做错了什么吗?
But this one function, called inToPos(char string[]) which is responsible to convert the inFix expression in the string inFix to the post fix expression in the string postFix using stacks, is creating a breakpoint. Can you guys help me out and tell me what I'm doing wrong?
这些是我的代码,非常需要你的帮助.. :)
These are my codes that badly needs your help.. :)
#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 是使用这个算法创建的:
Note the function inToPos was made using this algorithm:
- 从左到右扫描中缀字符串.
- 初始化一个空栈.
- 如果扫描的字符是操作数,则将其添加到后缀字符串中.如果扫描的字符是运算符并且堆栈为空将字符推入堆栈.
- 如果扫描到的字符是 Operator 且栈不为空,比较字符的优先级和上面的元素堆栈(topStack).如果 topStack 的优先级高于扫描的字符弹出堆栈 else 将扫描的字符推送到堆.只要stack不为空且topStack就重复此步骤优先于字符.重复此步骤直到字符被扫描.
- (扫描完所有字符后,我们必须添加任何字符堆栈可能必须到后缀字符串.)如果堆栈不为空,则添加topStack 到 Postfix 字符串并弹出堆栈.重复此步骤为只要堆栈不为空.
- 返回后缀字符串.
推荐答案
您确实应该学习如何使用调试器,它是解决此类问题的绝佳工具.但是,我运行了它并找出了您的问题:
You really should learn how to use a debugger, it's a great tool for figuring out problems like these. However, I ran it and figured out your problem:
在这一行:
while(precedence(list->top->data)<=precedence(string[i])){
在遍历列表时,每次都需要检查堆栈是否为空,而不仅仅是在进入循环之前.所以,做这样的事情:
When you're iterating through the list, you need to check whether the stack is empty each time, not only before you go into the loop. So, do something like this:
while(!isEmpty(list) && precedence(list->top->data)<=precedence(string[i])){
相反.
这篇关于使用堆栈中缀到 Postfix的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!