#include<stdio.h> #include<stdlib.h> #include<stdlib.h> //链栈 typedef struct node { char item[30]; struct node* next; }Node; typedef struct stack { Node *top; }Stack; //队列 typedef struct queueNode { char item[30]; struct queueNode* next; }QueueNode; typedef struct queue { QueueNode *front; QueueNode *rear; }Queue; //初始化栈 Stack* InitStack() { Stack *s = (Stack *)malloc(sizeof(Stack)); s->top = NULL; return s; } //判断栈是否为空 int StackEmpty(Stack *s) { if (s->top == NULL) return 1; else return 0; } //创建节点，入栈时用 Node *MakeNode(char *data) { Node *pNode; pNode = (Node *)malloc(sizeof(Node)); strcpy(pNode->item, data); pNode->next = NULL; return pNode; } //入栈 void Push(char *item, Stack *s) { Node *pNode = MakeNode(item); pNode->next = s->top; s->top = pNode; } //出栈 void Pop(char *item, Stack *s) { Node *pNode; if (!StackEmpty(s)) { pNode = s->top; strcpy(item, pNode->item); s->top = pNode->next; free(pNode); } } //创建链队列的节点 QueueNode* MakeQueueNode(char *item) { QueueNode *pNode; pNode = (QueueNode *)malloc(sizeof(QueueNode)); strcpy(pNode->item, item); pNode->next = NULL; return pNode; } //初始化队列 Queue* InitQueue() { Queue *q = (Queue *)malloc(sizeof(Queue)); q->front = q->rear = NULL; return q; } //队列是否空 int QueueEmpty(Queue *q) { if (!q->front) return 1; else return 0; } //入队操作 void Append(char *item, Queue *q) { QueueNode *pNode = MakeQueueNode(item); if (QueueEmpty(q)) { q->front = q->rear = pNode; } else { q->rear->next = pNode; q->rear = pNode; } } //出队 void Serve(char *item, Queue *q) { QueueNode *pNode; pNode = q->front; strcpy(item, pNode->item); q->front = pNode->next; free(pNode); } //判断运算符优先级 int Priority(char opr) { switch (opr) { case '(': return 0; case '-': case '+': return 1; case '*': case '/': return 2; } } //计算 void Caculate(Queue *q) { char temp[20], opr[20], num[20]; double fa, fb; Stack *stack_num = NULL; stack_num = InitStack(); while (!QueueEmpty(q)) { Serve(opr, q); if ((opr[0] >= '0'&&opr[0] <= '9') || (opr[0] == '.')) Push(opr, stack_num); else { Pop(num, stack_num); fb = atof(num); //atof将字符转成数字 Pop(num, stack_num); fa = atof(num); switch (opr[0]) { case '+': fa += fb; break; case '-': fa -= fb; break; case '*': fa *= fb; break; case '/': fa /= fb; break; } sprintf(num, "%f", fa); //将数字再转成字符 Push(num, stack_num); } } Pop(num, stack_num); printf("结果是:\n%s", num); } //遍历队列 void PrintQueue(Queue *q) { QueueNode *pNode; if (!QueueEmpty(q)) { printf("\nQueue:"); pNode = q->front; while (pNode) { printf("%s,", pNode->item); pNode = pNode->next; } } } //遍历栈 void PrintStack(Stack *s) { Node *pNode; if (!StackEmpty(s)) { printf("\nStack:"); pNode = s->top; while (pNode) { printf("%s,", pNode->item); pNode = pNode->next; } } } int main() { //下面是把输入的表达式转成后缀表达式，输入3-5*2则转成352*- char sExpression[100], temp[20], opr[20]; int i, j, isNum; Stack *stack_opr = NULL; //用来存运算符 Queue *queue_exp = NULL; //队列用来存后缀表达式 printf("输入表达式:\n"); gets(sExpression); printf("%s", sExpression); stack_opr = InitStack(); queue_exp = InitQueue(); i = 0; while (sExpression[i] != '\0') { isNum = j = 0; while (sExpression[i] >= '0'&&sExpression[i] <= '9')//如果输入的是数字 { isNum = 1; temp[j] = sExpression[i]; //将数字放入临时的temp i++; j++; } if (isNum) { temp[j] = '\0'; Append(temp, queue_exp); //入队列，转后缀表达式时，如果是数字直接进队列 } else //是操作符的话 { temp[0] = sExpression[i++]; temp[1] = '\0'; //截断字符串 switch (temp[0]) //根据操作符，比较和栈内的操作符优先级，进行入栈还是出栈操作 { case '(': Push(temp, stack_opr); break; case '+': case '-': case '*': case '/': if (!StackEmpty(stack_opr)) while (Priority(temp[0]) <= Priority(stack_opr->top->item[0]))//小于或等于栈内的操作符 { Pop(opr, stack_opr); Append(opr, queue_exp); if (StackEmpty(stack_opr)) break; } Push(temp, stack_opr); break; case ')': while (stack_opr->top->item[0] != '(') { Pop(opr, stack_opr); Append(opr, queue_exp); } Pop(opr, stack_opr); break; } } // PrintStack(stack_opr); // PrintQueue(queue_exp); } while (!StackEmpty(stack_opr)) //将表达式剩下的入队列 { Pop(opr, stack_opr); Append(opr, queue_exp); } Caculate(queue_exp); //计算后缀表达式 // PrintStack(stack_opr); // PrintQueue(queue_exp); system("pause"); }