大家好，又见面了，我是你们的朋友全栈君。

数据结构：表达式求值

表达式求值是程序设计语言编译的一个最基本问题，其中任何一个表达式都是由操作数、运算符(±*/)、界限符(#,(,),[,] )组成。运算符和界限符统称算符。算符的优先级关系为(数学角度上)：

为了通过代码实现，我们定义两个工作栈，一个叫OPTR，存运算符和界限符；另一个存OPND，存操作数或运算结果。
首先OPND为空栈，OPTR首先存’#’为栈底元素。
依次读取算术表达式，如果是操作数，存OPND；如果是运算符或界限符，则和OPTR的栈顶元素比较优先级，如果优先级高，存入栈，如果优先级低，则进行运算操作。。。

#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100//存储空间初始分配量 
#define STACKINCREMENT 10//分配增量
typedef int Status;
typedef char ElemType;
typedef struct{ 

ElemType *base;
ElemType *top;
int stacksize;
}sqStack; 
Status InitStack(sqStack &s){ 

s.base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!s.base){ 

exit(1);
}
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return 0;
}
ElemType GetTop(sqStack s){ 
//获取栈顶元素 
ElemType e;
if(s.top==s.base){ 

return 0;
}
e=*(s.top-1);
return e;
}
Status Push(sqStack &s,ElemType e){ 
//插入元素e为新的栈顶元素 
if(s.top-s.base>=s.stacksize){ 
//如果栈满，扩充空间 
s.base = (ElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!s.base){ 

exit(1);
}
s.top=s.base+s.stacksize; 
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;//赋值后栈顶指针+1 
return 0;
}
Status Pop(sqStack &s,ElemType &e){ 
//删除栈顶元素 
if(s.top==s.base){ 

return 1;
}
e = *--s.top;//栈顶指针-1，给e赋值 
return 0;
}
Status In(ElemType c){ 

if(c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c=='('||c==')'||c=='['||c==']')
return 1;
else
return 0;
}//In
char Precede(ElemType a, ElemType b){ 
//判断运算符栈的 栈顶元素a和读入元素b的优先级 
if(a=='+'||a=='-'){ 

if(b=='+'||b=='-'||b=='>'||b=='#'||b==')'||b==']')
return '>';
else return '<';
}
if(a=='*'||a=='/'){ 

if(b=='('||b=='[')
return '<';
else return '>';
}
if(a=='('){ 

if(b==')')
return '=';
else return '<';
}
if(a=='['){ 

if(b==']')
return '=';
else return '<';
}
if(a=='#'){ 

if(b=='#')
return '=';
else return '<';
}
}//Precede
ElemType Operate(ElemType a, ElemType x, ElemType b){ 
//进行运算的函数 
switch (x){ 

case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
}
}//Operator
ElemType EvaluateExpression(){ 

sqStack OPTR,OPND;//OPTR:运算符栈 OPND:运算数栈 
char c,x;
InitStack(OPTR);
Push(OPTR,'#'); 
InitStack(OPND);
c=getchar();
while(c!='#'||GetTop(OPTR)!='#'){ 

if(!In(c)){ 

Push(OPND,c-'0'); //不是运算符，进入运算数栈。 
c=getchar();
}
else
switch(Precede(GetTop(OPTR),c)){ 

case '<':Push(OPTR,c);c=getchar();break;//栈顶元素优先级低 
case '=':Pop(OPTR,x);c=getchar();break;//栈顶元素优先级低 
case '>':
Pop(OPTR,x);
ElemType a, b;
Pop(OPND, b);
Pop(OPND, a);
Push(OPND, Operate(a, x, b));
break;
}
}
return GetTop(OPND);
}
int main(){ 

printf("%d",EvaluateExpression());
return 0;
}