前段时间学习了栈的基础操作后，想着用栈实现四则运算来巩固以下所学知识。
什么是栈栈(Stack)是规定只能在表尾进行插入和删除操作的线性表。这一规定决定了栈中数据具有后入先出的特点。
由图可知，可以通过栈顶元素、存储元素、栈的最大空间来一起描述一个栈。对于顺序栈，存在一个定义栈的最大空间的参数使顺序栈具有固定的大小。如果想要一个没有存储元素个数限制的栈，则可以模仿动态链表的思路，让栈中元素包含有一个指向下一个元素地址的指针，从而形成一个链栈，这也正是实现四则运算所需要的。
实现思路 首先是实现要用到的栈的操作，分别是元素入栈、元素出栈、获取栈顶元素栈的基本定义：
typedef enum Status
{
ERROR = 0,
SUCCESS = 1
} Status;
typedef struct StackNode
{
int data;
struct StackNode *next;
}Node;
typedef struct StackInfo
{
struct StackNode *top;
int count;
}Stack;
入栈
1、形成新结点
2、新节结点的直接后继指向当前的栈顶元素
3、栈顶指针指向新结点
Status Push(Stack *s, int e)
{
if (s == NULL)
{
return ERROR;
}
Node *p = (Node *)malloc(sizeof(Node));
if (p == NULL)
{
return ERROR;
}
p->data = e;
p->next = s->top;
s->top = p;
s->count = s->count + 1;
return SUCCESS;
}
出栈
1、判断栈顶是否为空
2、p指向栈顶元素，栈顶指针下移一位
3、释放p所指向的空间
Status Pop(Stack *s)
{
if (s == NULL)
{
return ERROR;
}
if (s->top == NULL)
{
return ERROR;
}
int save;
Node *p = s->top;
save = s->top->data;
s->top = p->next;
free(p);
p = NULL;
s->count = s->count - 1;
return save;
}
得到栈顶元素
Status GetTop(Stack *s)
{
if (s == NULL)
{
return ERROR;
}
if (s->top == NULL)
{
return ERROR;
}
return s->top->data;
}
栈的判空
Status EmptyStack(Stack *s)
{
if (s == NULL)
{
return ERROR;
}
if(s->top == NULL)
{
return SUCCESS;
}
else{
return ERROR;
}
}
接下来，先理解以下四则运算的实现原理
观察式子：1+2 = 3
平时我们所用的四则运算表达式都是运算符在两个数字中间的，所以称这种表达式为中缀表达式。
而后缀表达式定义为运算符在两个数字之后的表达式。例如：
式子「1」：6 + ( 4 - 2 ) × 3 + 9 ÷ 3 = 15
式子「2」：6 4 2 - 3 × + 9 3 ÷ + = ？
式子「1」是中缀表达式，式子「2」是后缀表达式
与中缀表达式相比，后缀表达式的优点是不需要考虑括号匹配、运算符优先级和简化运算。
我们利用链栈来表示后缀表达式，从而可以计算出结果。所以首先要将中缀表达式转换为后缀表达式，方法如下：
从头到尾读取中缀表达式的每个对象，对不同对象按不同情况处理。
1 运算数：直接输出
2 左括号：压入堆栈
3 右括号：将栈顶元素弹出直到遇到左括号（出栈，不输出）
4 运算符：
若优先级大于栈顶元素，将它压栈
若优先级小于栈顶元素，栈顶元素弹出并输出；再比较新的栈顶元素，直到该运算符大于栈顶运算符优先级为止，然后将该运算符号压栈
5 各对象处理完毕后，把堆栈中存留的运算符一并输出
优先级如代码所示：
int Priority(char ch)
{
switch(ch)
{
case '(':
return 3;
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
default:
return 0;
}
}
接下来是后缀表达式的运算
规则：(用栈来进出运算的数字)
1.从左到右遍历后缀表达式的每一个数字和符号
2.若是数字，则进栈
3.若是符号，则把处于栈顶的两个数字出栈，进行运算
4.运算结果进栈
5.直到获得最终结果
