使用堆栈中缀到后缀 [英] 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("
");
}
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]!=' ';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:
- 从左到右扫描中缀字符串.
- 初始化一个空堆栈.
- 如果扫描的字符是操作数，则将其添加到 Postfix 字符串中.如果扫描的字符是运算符并且堆栈为空将角色推入堆栈.
- 如果扫描的字符是运算符并且堆栈不为空，将字符的优先级与顶部的元素进行比较堆栈(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])){
改为.
这篇关于使用堆栈中缀到后缀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
