这是我第一次学习编程。我是大学一年级的学生。我的专业是软件工程。这是我在软件课上的第三个作业。老师希望这个程序从命令行读入一个中缀表达式并输出一个后缀表达式。我们应该使用“Shunting Yard 算法”。我们应该有 2 个链表队列和 1 个链表堆栈。2 个用于保存输入和输出的队列和一个用于保存运算符的堆栈。我们还应该编写我已经做过的通用入队、出队、弹出、推送功能。
调车场算法：
- 将参数放入输入队列
- 从输入队列中取出令牌
- 如果 oprand(number)，添加到输出队列
- if 运算符，只要堆栈上的顶部运算符具有更高或相等的优先级，就将弹出运算符从堆栈中弹出并添加到输出队列，然后将新运算符压入堆栈
- 只要令牌仍在输入中，就返回步骤 1
- 从堆栈中弹出剩余的运算符并添加到输出队列
程序应按如下方式运行： programename 34 / 5 + 16 * 2 后缀：34 5 / 16 2 * + 我们还应该在每个输出之间留出空格
作为初学者，这对我来说太难了。我已经在这个程序上花费了三十多个小时。但该程序不起作用。程序继续在 main 函数的“while”循环中运行并且永不停止。如果有人可以帮助我，我会非常感激。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct listnode {
//Define structure of the node
char *element;
struct listnode* pnext;
};
struct Stack {
//Define structure of the stack
struct listnode* ptop;
};
struct Queue {
//Define structure of the queue
struct listnode* pfront;
struct listnode* prear;
};
void push (struct Stack* stack,char* element);
char* pop (struct Stack* stack);
void enqueue(struct Queue* queue,char* element);
char* dequeue(struct Queue* queue);
void s_travel(struct Stack* stack);
void q_travel(struct Queue* stack);
int precedence(char* x);
int empty(struct Stack* stack);
char* peek(struct Stack* stack);
int main (int argc,char *argv[]) {
struct Stack stack;
struct Queue input_queue;
struct Queue output_queue;
stack.ptop = NULL;
input_queue.pfront = NULL;
input_queue.prear = NULL;
output_queue.pfront = NULL;
output_queue.prear = NULL;
if (argc<3) {
//If the arguments is less then 3, unavailable input
printf("Input error");
return -1;
}
int i=0;
//Put all the arguments into the input_queue
for (i=1;i<argc;i++) {
enqueue(&input_queue,argv[i]);
}
printf("infix expression is : ");
q_travel(&input_queue);
printf("at the beginning, the peek of the stack is %s \n",peek(&stack));
for (i=1;i<argc;i++) {
//Token from input_queue
char *token;
char *x;
token = dequeue(&input_queue);
if(atof(token)) {
//If the element is a number,put it into output_queue
enqueue(&output_queue,token);
}
else {
/*If the element is a operator, c
* ompare the precedence of the top element of the stack and the precedence of token element
*/
char *peek1;
peek1=peek(&stack);
while ((precedence(peek1) >= precedence(token)) && (peek1 != NULL)){
/*while the precedence of the top element of the stack is greater
and equal to the precedence of token element*/
printf("inside,the top of the stack is %s \n",peek1);
//Pop element out of the stack and put it into output_queue
x = pop(&stack);
printf("after pop,x is %s,the top of the stack is %s \n",x,peek1);
enqueue(&output_queue,x);
}
//Then, push the new operator(token) into the stack
push(&stack,token);
}
}
while(peek(&stack)!=NULL) {
//Enqueue remaining operator from stack into output_queue
char *elem = pop(&stack);
enqueue(&output_queue,elem);
}
printf("Postifx expression is :\n");
q_travel(&output_queue);
return 0;
}
void push (struct Stack* stack,char* element) {
//Allocate a new node
struct listnode* new_node = (struct listnode *)malloc(sizeof(struct listnode));
new_node->element = element;
//Add new node at the top of the stack
new_node->pnext = stack->ptop;
stack->ptop = new_node;
}
char* pop (struct Stack* stack_buffer) {
//If the stack is not empty
if (stack_buffer->ptop) {
//Create a temporary node to replace top(removed) node
struct listnode *pelem = stack_buffer->ptop;
//The top pointer points to the next node
stack_buffer->ptop = pelem->pnext;
//Store the element of the removed node
char *elem = pelem->element;
//Remove node from memory
free(pelem);
//Return the element of the node that we removed
return elem;
}
//If the stack is empty, removing element fails,return -1
else {
return NULL;
}
}
void enqueue(struct Queue* queue,char *element) {
//Allocate a new node
struct listnode *new_node = (struct listnode *)malloc(sizeof(struct listnode));
new_node->element = element;
new_node->pnext = NULL;
//If the queue is not empty,add new node at the end of the queue
if (queue->prear) {
queue->prear->pnext = new_node;
}
//If the queue is empty,add new node at front of the queue
else {
queue->pfront = new_node;
}
//Added node becomes new rear node
queue->prear = new_node;
}
char* dequeue(struct Queue* queue) {
/*Create a temporary node to replace the front node of the queue
struct listnode *pelem = queue->pfront;*/
//If the queue is not empty
if (queue->pfront) {
//Store the element of the front node
char *elem = queue->pfront->element;
//The front pointer points to the next node
queue->pfront = queue->pfront->pnext;
//If the queue only has one node
if(pelem == queue->prear) {
//After removing the only node, the queue becomes empty
queue->prear = NULL;
}
//Remove node from memory
free(pelem);
//Return the element of the node that we removed
return elem;
}
//If the queue is empty, removing node fails,return NULL
else {
return NULL;
}
}
void s_travel(struct Stack* buffer) {
//Function to print out the element in the stack
//Create a temporary node to replace the top node of the stack
struct listnode* elem = buffer->ptop;
while(elem != NULL) {
printf("%s ", elem->element);
elem = elem->pnext;
}
printf("\n");
}
void q_travel(struct Queue* buffer) {
//Function to print out the element in the queue
//Create a temporary node to replace the front node of the stack
struct listnode* elem = buffer->pfront;
while(elem != NULL) {
printf("%s ", elem->element);
elem = elem->pnext;
}
printf("\n");
}
int precedence(char* operator) {
/*Function to determine the precedence of the operator,prior operator has greater return value*/
printf("entering precedence with %s \n",operator);
if (operator == NULL) {
return -1;
}
else if (strcmp(operator,"(")==0){
printf("Pr: %s 0\n",operator);
return 0;
}
else if (strcmp(operator,"+")==0||strcmp(operator,"-")==0) {
printf("Pr: %s 1\n",operator);
return 1;
}
else if ( (strcmp(operator,"*")==0) || (strcmp(operator,"/")==0) || (strcmp(operator,"%")==0) || (strcmp(operator,"x")==0) ) {
printf("Pr: %s 2\n",operator);
return 2;
}
else {
return -2;
}
return -3;
}
int empty(struct Stack* stack) {
//Function to check if the stack is empty
//If the stack is empty, the return value would be 1;otherwise, it would be 0
return NULL == stack->ptop;
}
char* peek(struct Stack* stack) {
//Function to find out the top element of the stack
//If the stack is empty, return NULL
if (empty(stack)) {
return NULL;
}
//If the stack is not empty, return the top element of the stack
char* elem = stack->ptop->element;
return elem;
}