栈结构是一种特殊的线性表，限定仅在表的一端进行元素的插入和删除。本文使用C语言利用栈结构实现表达式解析并求值功能。
一、表达式求值
表达式求值在编译程序和计算程序中被经常应用，表达式本身是一个字符序列，要实现对表达式求值，首先要能够正确解释表达式。在编程语言中，表达式是由变量、常量和运算符的组合，它执行计算并返回计算结果。在表达式中运算符作用的变量或常量称为操作数。例如，求圆面积的公式就是一个表达式，其中S、π、r为变量或常量，r的2次方可以描述为r*r。求圆面积的表达式为：
S =π* r *r;正确地解释表达式，就是让程序扫描表达式字符序列时，从字符序列中正确解析出操作数、运算符、界限符，并按照运算规则执行运算。例如，要对下面的算术表达式求值
2*（3+5）程序不仅要识别出2、3、5操作数，还需要识别出*、+、（、）运算符。同时还要按照算术四则运算的规则执行运算。既先乘除，后加减；从左算到右；先括号内，后括号外。
为了叙述简便，本文仅讨论简单算术表达式的求值问题，运算符也限于加、减、乘、除四中运算符，界限符仅限于小括号。读者不难将它推广到更一般的表达式上。
二、栈结构
要对上面的表达式求值，可以采用算符优先法。它的实现思想是对表达式字符序列自左向右进行扫描，遇到操作数入操作数栈。遇到运算符，首先与运算符栈的栈顶运算符比较优先级，若栈顶运算符的优先级高于当前运算符，则栈顶运算符出栈并执行运算，否则将当前运算符入运算符栈，直至整个表达式求值完毕。
栈结构是一种特殊的线性表，限定仅在表的一端进行元素的插入和删除。当表中没有元素时，称为空栈。若给定栈：
S = (a1，a2，……，an)
则称a1是栈底元素，an是栈顶元素，表中元素按a1，a2，……，an的次序进栈，出栈的顺序是an，……，a2，a1。也就是说，栈结构的元素访问原则是后进先出，也称为后进先出的线性表的，如下图所示。
栈结构运算有入栈、出栈、访问栈顶元素、栈置空四种基本运算。
（1）入栈运算
该运算在长度为n的栈中，将元素置入栈顶。若栈已满，返回出错信息。
（2）出栈运算
该运算在长度为n的栈中，取出栈顶元素，并从栈中删除该元素。若栈为空，返回出错信息。
（3）访问栈顶元素运算
该运算在长度为n的栈中，取出栈顶元素。若栈为空，返回出错信息。
（4）栈置空运算
该运算将栈置为空栈。
三、算法设计
算式由操作数、运算符和界限符组成，操作数为需要执行运算的数，运算符为加、减、乘、除，界限符为小括号。
算符优先法是根据算式相继出现的算符优先级来确定运算顺序，要比较算符的优先级，就要确定各种算符的优先级别，可以将算符间的优先级通过矩阵表示，在解析算式过程中通过查询算符优先级矩阵获取算符间的优先关系。
算式的运算符和界限符统称为算符，它们组成一个集合op{ +，-，*，/，(，) }。集合中任意两个算符a或b的优先级至多是下面三种关系之一。
a < b a的优先级小于b的优先级
a = b a的优先级等于b的优先级
a > b a的优先级大于b的优先级
在算符优先算法中，可以采用下面的矩阵定义op集合算符间的优先关系，其中a为栈顶运算符，b为当前识别的运算符。
算符间的优先矩阵可以用字符类型的二维数组表示。
在C语言中，算符间的优先矩阵可以字符类型的二维数组表示。
/**
运算符
*/
char oparray[]={'+','-','*','/','(',')'};
/**
运算符优先级
*/
char priority[6][6]={
{'>','>','>','>','<','>'},
{'>','>','>','>','<','>'},
{'<','<','<','<','<','>'},
{'<','<','<','<','<','>'},
{'<','<','<','<','<','='},
{'>','>','>','>','=','='}
};解析表达式时可以使用操作数和运算符两个栈，操作数栈用于存储操作数和运算结果，运算符栈用于存储算符。
算法的基本思想是：依次读入表达式每个字符，如是操作数进操作数栈，如是运算符，需要和运算符栈的栈顶运算符比较优先级，优先级若低于栈顶运算符，首先需要处理栈顶运算符并执行相关运算后再入栈，直至整个算式求值完毕。
四、代码实现
下面用C语言给出算法程序代码，程序假定输入的算式语法正确，没有对算式语法进行检测。
float evaluate(char* expression)
{
int length = strlen(expression);
int i,j;
char *p;
char ch,ch1,ch2,op;
double temp;
// 运算符栈
PSTACK pStackOp = (PSTACK)init_stack(0);
// 操作数栈
PSTACK pStackNum = (PSTACK)init_stack(0);
for( i = 0; i < length; i++ )
{
if( expression[i]==' ' )
continue;
if (expression[i] >= '0' && expression[i] <= '9')
{
p = (char*)malloc(sizeof(char)*length);
j = 0;
while(i < length && expression[i] >= '0' && expression[i] <= '9')
{
p[j++] = expression[i++];
}
p[j] = '\0';
i--;
temp = atof(p);
// 操作数入栈
push(pStackNum,0,&temp);
}
if( isOperator(expression[i]) )
{
// 判断运算符栈是否为空
if( isEmpty(pStackOp) )
{
// 运算符入栈
push(pStackOp,1,&expression[i]);
}
else
{
// 判断字符的优先级
ch1 = *((char*)peek(pStackOp,1));
ch = hasPrecedence(expression[i],ch1);
if( ch == '<' )
{
// 运算符入栈
push(pStackOp,1,&expression[i]);
}
else if( ch == '>' )
{
if( expression[i] == ')' )
{
while(1)
{
if( isEmpty(pStackOp) )
break;
ch2 = *((char*)peek(pStackOp,1));
op = hasPrecedence(expression[i],ch2);
if( op == '=' )
{
pop(pStackOp,1);
break;
}
else
{
temp = caculate(*((char*)pop(pStackOp,1)),*((double*)pop(pStackNum,0)),*((double*)pop(pStackNum,0)));
push(pStackNum,0,&temp);
}
}
}
else
{
temp = caculate(*((char*)pop(pStackOp,1)),*((double*)pop(pStackNum,0)),*((double*)pop(pStackNum,0)));
push(pStackNum,0,&temp);
push(pStackOp,1,&expression[i]);
}
}
}
}
}
while(!isEmpty(pStackOp))
{
temp = caculate(*((char*)pop(pStackOp,1)),*((double*)pop(pStackNum,0)),*((double*)pop(pStackNum,0)));
push(pStackNum,0,&temp);
}
return *((double*)pop(pStackNum,0));
}函数evaluate()是算法的核心，传入的参数expression是待求值的表达式。函数evaluate()基本体现了前面给出的算法思想。其中对小括号做了特殊处理，当遇到算符')'时，需要对算符栈连续执行出栈操作，并执行相关运算，直至与栈顶运算符优先级相等或者栈已空。
在函数evaluate()内部调用了一些已定义的函数，下面对这些函数给出说明。
isOperator()函数判断传入的字符是否为运算符，若为运算符返回1，否则返回0。
int isOperator(char op)
{
int i;
for(i = 0; i < sizeof(oparray)/sizeof(oparray[0]); i++ )
{
if( op == oparray[i] )
return 1;
}
return 0;
}getOperator()函数获取运算符在数组中的索引，代码如下：
int getOperator(char op)
{
int i;
for(i = 0; i < sizeof(oparray)/sizeof(oparray[0]); i++ )
{
if( op == oparray[i] )
return i;
}
return -1;
}hasPrecedence()函数用于判断两个算符的优先级关系，算符的优先级矩阵由priority二维数组给出，函数返回矩阵给出的优先级关系。
char hasPrecedence(char op1, char op2)
{
int suffixop1 = getOperator(op1);
int suffixop2 = getOperator(op2);
if( suffixop1 == -1 || suffixop2 == -1 )
return 0;
return priority[suffixop1][suffixop2];
}caculate()函数对传入的运算符和操作数做求值运算。代码如下：
float caculate(char op, float b, float a)
{
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0) {
return 0;
}
return a / b;
}
return 0;
}函数evaluate()内部还调用了peek()、isEmpty()函数。peek()函数从栈中获取栈顶运算，但不弹出元素，peek()函数的代码可以借鉴pop()函数，由读者自行给出。isEmpty()函数判断栈是否为空，栈结构的top成员为-1时，该栈为空，isEmpty()函数的代码由读者自行给出。