//栈的应用--中缀表达式#define _CRT_SECURE_NO_WARNINGS#include#include #include #include"linkstack.h"/*遍历中缀表达式中的数字和符号对于数字：直接输出对于符号： 左括号：进栈 运算符号：与栈顶符号进行优先级比较 若栈顶符号优先级低：此符合进栈 （默认栈顶若是左括号，左括号优先级最低） 若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈 右括号：将栈顶符号弹出并输出，直到匹配左括号遍历结束：将栈中的所有符号弹出并输出*///是否是左括号int IsLeft(char ch){ if (ch == '(') { return 0; } return 1;}//是否是右括号int IsRight(char ch){ if (ch == ')') { return 0; } return 1;}//是否是数字int IsNumber(char ch){ if (ch <= '9'&&ch >= '0') { return 0; } return 1;}//是否是运算符int IsOperator(char ch){ if (ch == '+' || ch == '-' || ch == '*' || ch == '/') { return 0; } return 1;}//优先级比较--不考虑左括号 右括号int Priority(char ch){ if (ch == '-' || ch == '+') { return 1; } if (ch == '*' || ch == '/') { return 2; } //默认栈顶若是左括号，左括号优先级最低 if (ch == '(') { return 0; } return 0;}void Test(){ char *str = "8+(3-1)*5"; int ret = 0; //创建一个链表栈 LinkStack* stack = LinkStack_Create(); if (stack == NULL) { printf("链表创建失败"); } //遍历字符串 while (*str){ //判断是否是数字 if (IsNumber(*str) == 0) { //直接打印 printf("%c", *str); } //判断左括号--直接进栈 if (IsLeft(*str) == 0) { //直接进栈 /* 此时str指针存放在常量区，在这个函数中 str指针指向的字符地址一直存在，并且内容不会改变 */ LinkStack_Push(stack, str); } //判断右括号 --出栈，直至匹配到左括号 if (IsRight(*str) == 0) { //出栈 while (LinkStack_Size(stack) > 0){ //弹出栈顶元素 char *temp1 = (char *)LinkStack_Pop(stack); if (temp1 == NULL) { printf("栈中数据没有匹配\"(\"！\n"); goto END; } //直至匹配左括号 if (*temp1 == '(') { break; } //打印输出符号--不是左括号打印，是括号不打印 printf("%c", *temp1); /* 此处不用释放内存 因为我并没有malloc内存 */ } } //判断是否是运算符 if (IsOperator(*str) == 0) { //优先级判断 while (LinkStack_Size(stack) > 0){ /* 不断获取栈顶元素 与插入的优先级 插入优先级高 直接入栈 不高 弹出栈顶元素 */ //获取栈顶元素 char *temp1 = (char *)LinkStack_Top(stack); //比较优先级 栈顶优先级不低于入栈元素 直接出栈 直到栈顶元素的优先级低于入栈元素 if (Priority(*str) <= Priority(*temp1)) { //弹出栈顶元素 char *temp2 = (char *)LinkStack_Pop(stack); if (temp2 == NULL) { printf("栈中数据有问题！\n"); goto END; } //打印栈顶元素 printf("%c", *temp2); } else{ //否则跳出循环 break; } } //此时栈顶元素的优先级比入栈元素优先级要低 //可以入栈 LinkStack_Push(stack, str); } str++; } //字符串遍历结束 将栈中符号全部弹出 while (LinkStack_Size(stack) > 0){ //弹出栈顶元素 char *temp1 = (char *)LinkStack_Pop(stack); if (temp1 == NULL) { printf("栈中数据有问题！\n"); goto END; } //打印栈顶元素 printf("%c", *temp1); } //销毁链表END: ret = LinkStack_Destroy(&stack); printf("\n");}void main(){ Test(); system("pause");}
