中缀表达式求值
所用知识：C语言，堆栈操作
算法思想来自慕课浙江大学《数据结构》陈老师，何老师
笔记：
1.堆栈：
1.1 引子
一种数据结构，在函数调用，表达式求值等都有广泛的应用
中缀表达式：a+b*c-d/e:生活中经常使用，但是计算机不好识别
后缀表达式：abc*+dc/-:生活中不好使用，但计算机容易识别
例：
总结：因此需要一种存储方法，能顺序的存储运算数，在需要时倒叙输出。-->堆栈有
堆栈的特点：后入先出。
1.2堆栈的操作
操作集：长度为maxSize的堆栈S ==> stack,堆栈的元素elementType，那么如下的操作
stack createStack(int maxSize);//生成空堆栈，其最大长度为maxSize
int isFull(stack s,int maxSize);//判断栈s是否为空
void push(stack s,elementType item);//将元素压入堆栈
int isEmpty(stack s);//判断堆栈是否为空
elementType pop(stack s);//删除并返回栈顶元素
1.2.1
用数组来表示堆栈的方法可以参照文件夹下面的同级目录的文件stackArray.c
同时还有使用一个数组来表示两个堆栈，twoStack.c
1.2.2使用链表来模拟堆栈
因为链表有两头，但是堆栈的头指针我们会选择链表的头节点，因为便于删除操作，尾节点不方便进行删除操作
下面是模拟的示意图
head(头指针，没有元素的) --> node1(top指针) --> node2(堆栈中的元素) --> node3 --> node4
代码可以见：stackLinkList.c
1.2.3 利用堆栈进行表达式求值
我们平时所见到的表达式都是中缀表达式，但是如果想求表达式的值，先把中缀表达着中文后缀表达式，
在利用堆栈对后缀表达式进行求值
中缀表达式转后缀表达式的思路；
首先看一个简单的：
中缀表达式：2 + 9 / 3 - 5 后缀表达式：2 9 3 / + 5 -
通过对比我们发现，中缀表达式和后缀表达式的数字顺序并没有发生改变，只是符号位置发生了改变
所以，我们可以构思，使用一个栈来存在运算符，遇到数字就输出，遇到符号就压栈，如果读入的符号比栈顶的符号
优先级高，就压栈，否则就弹栈并输出
下面是中缀表达式：2 + 9 / 3 - 5压栈和弹栈的具体步骤
输出 堆栈内元素
2
+
9
/(优先级比+高，压栈)
3
/ + -(首先弹出/,但是因为同级运行需要按照从左往右的运算，所以+也需要弹栈)
5 -
- (元素全部读取完毕以后，-弹栈)
所以中缀表达式：2 + 9 / 3 - 5的后缀表达式为 2 9 3 / + 5 -
但是如果遇到带有()的表达式怎么办：遇到"("把"("压入栈中，此时栈中的"("运算级别最低，在按照上面的运算符的运算规则来
进行压栈和弹栈。直到读取到")",才把"("弹栈，但是对"("和")"不进行输出
举个例子：
求下面中缀表达式：2 * (9+6/3-5)+4的后缀表达式
输出 堆栈内元素(top->bottom)
2
*
( *
9 + ( *
6
/ + ( *
3
- ( *(首先弹出/,但是因为同级运行需要按照从左往右的运算，所以+也需要弹栈,并输出)
/ +
5
- *(遇到")",把栈里依次弹出，直到遇到第一个"(",但是对"("和")"不进行输出)
* +(遇到+，先弹出*，然后输出)
4 +
+ NULL(没有元素可读，弹出堆栈中最后一个元素)
所以中缀表达式：2 * (9+6/3-5)+4的后缀表达式为: 2 9 6 3 / + 5 - * 4 +
代码实现
思路：中缀表达式先转后缀表达式在求值
只支持0-9之间的数字的+-*/以及(),支持括号里面嵌套括号，如3*(2*3-4*1+(3*5)/3)*3+2
不支持分开的括号3*(2*3-4*1+(3*5)/3)*3+2+(4/2)
如果有给出修改意见，感激不尽。写的比较匆忙，代码的复用性和注释的完整性可能不是很好
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<math.h> 5 #include<ctype.h> 6 #define MAXSIZE 100 7 8 9 #include<stdio.h> 10 #include<stdlib.h> 11 /*使用链表来模拟堆栈，*/ 12 13 14 15 /*=======================================================定义double类型的堆栈链式存储并进行相关的压栈，弹栈等操作===============================================================*/ 16 17 //定义double类型的堆栈的链式存储 18 typedef struct node3{ 19 double element; 20 struct node3 *next; 21 }integerSta,*pIntegerStack; 22 23 //构造一个double类型的链式栈 24 pIntegerStack createIntegerEmptyStack(){ 25 pIntegerStack stack; 26 stack = (pIntegerStack)malloc(sizeof(integerSta)); 27 if(stack){ 28 stack->next=NULL; 29 } 30 return stack; 31 } 32 33 //判断double类型的链式栈是否为空 34 int isIntegerEmpty(pIntegerStack stack){ 35 if(stack->next==NULL){ 36 return 1; 37 }else{ 38 return 0; 39 } 40 } 41 42 //压栈 43 void pushInteger(pIntegerStack stack,double element){ 44 pIntegerStack node = (pIntegerStack)malloc(sizeof(integerSta)); 45 node->element=element; 46 node->next=stack->next; 47 stack->next=node; 48 } 49 50 //弹栈 51 double popInteger(pIntegerStack stack){ 52 double element; 53 pIntegerStack topHead; 54 if(isEmpty(stack)){ 55 printf("the stack is empty,can not pop"); 56 return; 57 }else{ 58 topHead = stack->next; 59 stack->next = topHead->next; 60 element = topHead->element; 61 free(topHead); 62 return element; 63 } 64 } 65 66 //取栈顶元素 67 double getIntegetStackTopElement(pIntegerStack stack){ 68 return (stack->next->element); 69 } 70 71 //打印栈内元素 72 void toStringInteger(pIntegerStack stack){ 73 pIntegerStack top = stack->next; 74 printf("toString:"); 75 while(top!=NULL){ 76 printf("%f ",top->element); 77 top=top->next; 78 } 79 printf(" "); 80 } 81 82 83 84 85 /*================================================定义一个存储字符的线性表=========================================================================*/ 86 87 88 89 //构造一个线性表存储后缀表达式 90 typedef struct node2{ 91 char data[MAXSIZE]; 92 int length; 93 }li,*pList; 94 95 96 97 //初始化线性表 98 pList createEmptyList(){ 99 pList p; 100 p = (pList)malloc(sizeof(li)); 101 if(p){ 102 p->length=-1; 103 } 104 return p; 105 } 106 107 //向线性表中插入元素 108 void insert(pList list,char c){ 109 if(list){ 110 list->data[++(list->length)]=c; 111 } 112 } 113 114 //将线性表中的元素打印 115 void toStringList(pList list){ 116 int i; 117 for(i=0;i<=list->length;i++){ 118 printf("%c ",list->data[i]); 119 } 120 printf(" "); 121 122 } 123 124 125 126 /*==================================================定义一个字符栈并进行相关操作=================================================================*/ 127 //定义字符栈 128 typedef struct node{ 129 char element; 130 struct node *next; 131 }sta,*pStack; 132 133 //创建一个空的字符链式栈 134 pStack createEmptyStack(){ 135 pStack stack; 136 stack = (pStack)malloc(sizeof(sta)); 137 if(stack){ 138 stack->next=NULL; 139 } 140 return stack; 141 } 142 143 //判断链式栈是否为空 144 int isEmpty(pStack stack){ 145 if(stack->next==NULL){ 146 return 1; 147 }else{ 148 return 0; 149 } 150 } 151 152 //把元素压入栈 153 void push(pStack stack,char element){ 154 pStack node = (pStack)malloc(sizeof(sta)); 155 node->element=element; 156 node->next=stack->next; 157 stack->next=node; 158 } 159 160 //把元素弹栈 161 char pop(pStack stack){ 162 char element; 163 pStack topHead; 164 if(isEmpty(stack)){ 165 printf("the stack is empty,can not pop"); 166 return NULL; 167 }else{ 168 topHead = stack->next; 169 stack->next = topHead->next; 170 element = topHead->element; 171 free(topHead); 172 return element; 173 } 174 } 175 176 //获取栈顶元素 177 char getTopElement(pStack stack){ 178 if(isEmpty(stack)){ 179 printf("the stack is empty,can not get top element"); 180 return; 181 }else{ 182 return (stack->next->element); 183 } 184 } 185 186 187 188 /*=============================================中缀表达式转后缀表达式=====================================================================*/ 189 190 191 //打印字符数组 192 void charArrayToString(char *arr){ 193 char *p = arr; 194 while(*p!='