“栈”的典型应用—表达式求值（C语言实现）

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

表达式求值是程序设计语言编译中的一个基本问题。它的实现就是对“栈”的典型应用。本文针对表达式求值使用的是最简单直观的算法“算符优先法”。

我们都知道算术四则运算的运算规则是：

先乘除，后加减。

从左到右计算

先算括号内，再算括号外

表达式组成

任何一个表达式都有操作数、运算符和界定符组成。

操作数即可以是常量，也可以是被说明为变量或常量的标识符。

运算符可以分为算术运算，关系运算和逻辑运算符。

界定符有左右括号和结束符等。

本文为了方便演示只使用算术运算。

运算符优先级

对于连个相继出现的操作符θ₁和θ₂有三种关系：大于、等于和小于。由此可以列出“+-*/”之间的优先级。如下表：

	+	–	*	/	(	)	#
+	>	>	<	<	<	>	>
–	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	<	<	<	<	<	=
)	>	>	>	>		>	>
#	<	<	<	<	<		=

加减乘除优先性都低于“（”但是高于“）”，由运算从左到右可知，当θ₁=θ₂ ，令θ₁>θ₂

为了算法简洁，在表达式的左边和右边虚设一个“#”，这一对“#”表示一个表达式求值完成。

“（”=“）”当一对括号相遇时表示括号内已运算完成。

“）”和“（”、“#”和“(”、“(”和“#”无法相继出现如果出现则表达式出现语法错误。

为实现优先算法，可以使用两个工作栈，一个是OPTR，用于寄存运算符，一个是OPND，用于寄存运算数和运算结果。

算法基本思路。

首先置操作数栈为空栈，表达式起始符为“#”为栈底元素。

依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕（OPTR栈顶元素和当前读入的字符均为“#”）

代码实现：

首先先熟悉一下栈的相关操作：

#include "stdio.h"
#include "malloc.h"

#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW    -2

typedef int  Status;
#define STACK_INIT_SIZE  100
#define STACKINCREMENT   10

typedef struct{
    SElemType *base;
    SElemType *top;
    int      stacksize;
}SqStack;
//构造一个空栈
Status InitStack(SqStack *S){
    S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

    if(!S->base)
        exit(OVERFLOW);
    S->top=S->base;
    S->stacksize=STACK_INIT_SIZE;
    return OK;
}
//判断是否为空栈
Status StackEmpty(SqStack S){
    if(S.top == S.base)
        return TRUE;
    else
        return FALSE;
}
//用e返回S的顶元素
Status GetTop(SqStack S, SElemType *e){
    if(S.top == S.base)
        return ERROR;
    *e = *(S.top-1);
    return OK;
}
//插入e为新的顶元素
Status Push(SqStack *S, SElemType e){
    if((S->top - S->base) >= S->stacksize){
        S->base = (
                    SElemType*)realloc(S->base,
                   (S->stacksize+STACKINCREMENT)*sizeof(SElemType)
                   );
        if(!S->base)
            exit(OVERFLOW);
        S->top = S->base +S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top)=e;
    S->top++;
    return OK;
}
//删除S的顶元素，并用e返回其值
Status Pop(SqStack *S, SElemType *e){
    if(S->top == S->base)
        return ERROR;
    S->top--;
    *e = *(S->top);
    return OK;
}
//从栈底到栈顶依次对S的每个元素调用函数Visit（），一旦失败操作无效
Status ListTraverse(SqStack S,Status (*visit)(SElemType)){
    SElemType *p;
    p=S.base;
    for(p=S.base;p<S.top;p++)
        (*visit)(*p);

    return OK;
}
//输出元素e
Status output(SElemType e){
    printf("%d ",e);

    return OK;
}

实现表达式求值的代码：

/*计算整数表达式的值
 *表达式必须以#结束
 *表达式中可以出现多位数字，
 *表达式中可以出现空格
 *运算符包括+,-,*,/,(,)
 *运算结果可以是多位整数，并以整数的形式返回
 */
typedef int SElemType;      /*放入堆栈的元素的类型*/
#include <ctype.h>
#include "stack_s.c"
/*判断输入的某个字符是否是运算符
 *c表示输入的字符
 *op数组中存放系统能识别的运算符
 */
Status in(char c,char op[]){
    char *p;
    p=op;
    while(*p != '/*计算整数表达式的值
*表达式必须以#结束
*表达式中可以出现多位数字，
*表达式中可以出现空格
*运算符包括+,-,*,/,(,)
*运算结果可以是多位整数，并以整数的形式返回
*/
typedef int SElemType;      /*放入堆栈的元素的类型*/
#include <ctype.h>
#include "stack_s.c"
/*判断输入的某个字符是否是运算符
*c表示输入的字符
*op数组中存放系统能识别的运算符
*/
Status in(char c,char op[]){
char *p;
p=op;
while(*p != '\0'){
if(c == *p)
return TRUE;
p++;
}
return FALSE;
}
/*比较两个运算符的优先级
*a，b中存放待比较的运算符
*'>'表示a>b
*'0'表示不可能出现的比较
*/
char Precede(char a, char b){
int i,j;
char pre[][7]={         
/*运算符之间的优先级制作成一张表格*/
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'},
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='}};
switch(a){
case '+': i=0; break;
case '-': i=1; break;
case '*': i=2; break;
case '/': i=3; break;
case '(': i=4; break;
case ')': i=5; break;
case '#': i=6; break;
}
switch(b){
case '+': j=0; break;
case '-': j=1; break;
case '*': j=2; break;
case '/': j=3; break;
case '(': j=4; break;
case ')': j=5; break;
case '#': j=6; break;
}
return pre[i][j];
}
/*进行实际的运算
*a，b中分别以整数的形式存放两个待运算的操作数
*theta中存放代表操作符的字符
*结果以整数的形式返回
*/
int Operate(int a, char theta, int b){
int i,j,result;
i=a;
j=b;
switch(theta)   {
case '+': result = i + j; break;
case '-': result = i - j; break;
case '*': result = i * j; break;
case '/': result = i / j; break;
}
return result;
}
/*从输入缓冲区中获得下一个整数或运算符，并通过n带回到主调函数
*返回值为1表示获得的是运算符
*返回值为0表示获得的是整形操作数
*/
int getNext(int *n){
char c;
*n=0;
while((c=getchar())==' ');  /*跳过一个或多个空格*/
if(!isdigit(c)){            /*通过函数判断如果字符不是数字，那么只能是运算符*/
*n=c;
return 1;
}
do    {                         /*能执行到该条语句，说明字符是数字，此处用循环获得连续的数字*/
*n=*n*10+(c-'0');       /*把连续的数字字符转换成相对应的整数*/
c=getchar();
}    while(isdigit(c));         /*如果下一个字符是数字，进入下一轮循环*/
ungetc(c,stdin);            /*新读入的字符不是数字，可能是运算符,为了不影响下次读入，把该字符放回到输入缓冲区*/
return 0;
}
int EvaluateExpression(){
int n;
int flag;
int c;
char x,theta;
int a,b;
char OP[]="+-*/()#";
SqStack  OPTR;
SqStack  OPND;
InitStack(&OPTR);      
Push(&OPTR,'#');
InitStack(&OPND);
flag=getNext(&c);
GetTop(OPTR, &x);
while(c!='#' || x != '#')
{
if(flag == 0)
{
Push(&OPND,c);
flag = getNext(&c);
}        else
{
GetTop(OPTR, &x);
switch(Precede(x, c))
{
case '<'://栈顶元素优先级低                    
Push(&OPTR,c);
flag = getNext(&c);
break;
case '='://脱括号并接受下一字符 
Pop(&OPTR,&x);
flag = getNext(&c);
break;
case '>'：// 退栈并将运算结果入栈                                       
Pop(&OPTR, &theta);
Pop(&OPND,&b);
Pop(&OPND,&a);
Push(&OPND, Operate(a, theta, b));
break;
}
}
GetTop(OPTR, &x);
}
GetTop(OPND, &c);
return c;
}
void main(){
int c;
printf("Please input one expression:");
c=EvaluateExpression();
printf("Result=%d\n",c);
getch();
}
'){
        if(c == *p)
            return TRUE;
        p++;
    }
    return FALSE;
}
/*比较两个运算符的优先级
 *a，b中存放待比较的运算符
 *'>'表示a>b
 *'0'表示不可能出现的比较
 */
char Precede(char a, char b){
    int i,j;
    char pre[][7]={         
	/*运算符之间的优先级制作成一张表格*/
        {'>','>','<','<','<','>','>'},
        {'>','>','<','<','<','>','>'},
        {'>','>','>','>','<','>','>'},
        {'>','>','>','>','<','>','>'},
        {'<','<','<','<','<','=','0'},
        {'>','>','>','>','0','>','>'},
        {'<','<','<','<','<','0','='}};
    switch(a){
        case '+': i=0; break;
        case '-': i=1; break;
        case '*': i=2; break;
        case '/': i=3; break;
        case '(': i=4; break;
        case ')': i=5; break;
        case '#': i=6; break;
    }
    switch(b){
        case '+': j=0; break;
        case '-': j=1; break;
        case '*': j=2; break;
        case '/': j=3; break;
        case '(': j=4; break;
        case ')': j=5; break;
        case '#': j=6; break;
    }
    return pre[i][j];
}
/*进行实际的运算
 *a，b中分别以整数的形式存放两个待运算的操作数
 *theta中存放代表操作符的字符
 *结果以整数的形式返回
 */
int Operate(int a, char theta, int b){
    int i,j,result;
    i=a;
    j=b;

    switch(theta)   {
        case '+': result = i + j; break;
        case '-': result = i - j; break;
        case '*': result = i * j; break;
        case '/': result = i / j; break;
    }
    return result;
}
/*从输入缓冲区中获得下一个整数或运算符，并通过n带回到主调函数
 *返回值为1表示获得的是运算符
 *返回值为0表示获得的是整形操作数
 */
int getNext(int *n){
    char c;
    *n=0;
    while((c=getchar())==' ');  /*跳过一个或多个空格*/
    if(!isdigit(c)){            /*通过函数判断如果字符不是数字，那么只能是运算符*/
        *n=c;
        return 1;
    }
    do    {                         /*能执行到该条语句，说明字符是数字，此处用循环获得连续的数字*/
        *n=*n*10+(c-'0');       /*把连续的数字字符转换成相对应的整数*/
        c=getchar();
    }    while(isdigit(c));         /*如果下一个字符是数字，进入下一轮循环*/
    ungetc(c,stdin);            /*新读入的字符不是数字，可能是运算符,为了不影响下次读入，把该字符放回到输入缓冲区*/
    return 0;
}

int EvaluateExpression(){

    int n;
    int flag;
    int c;
    char x,theta;
    int a,b;

    char OP[]="+-*/()#";
    SqStack  OPTR;
    SqStack  OPND;

    InitStack(&OPTR);      
    Push(&OPTR,'#');
    InitStack(&OPND);
    flag=getNext(&c);

    GetTop(OPTR, &x);
    while(c!='#' || x != '#')
    {
        if(flag == 0)
	     {
                  Push(&OPND,c);
                  flag = getNext(&c);
             }        else
	{
            GetTop(OPTR, &x);
            switch(Precede(x, c))
	    {
                case '<'://栈顶元素优先级低                    
                    Push(&OPTR,c);
                    flag = getNext(&c);
                    break;
                case '='://脱括号并接受下一字符 
                    Pop(&OPTR,&x);
                    flag = getNext(&c);
                    break;
                case '>'：// 退栈并将运算结果入栈                                       
                    Pop(&OPTR, &theta);
                    Pop(&OPND,&b);
                    Pop(&OPND,&a);
                    Push(&OPND, Operate(a, theta, b));
                    break;
            }
        }
        GetTop(OPTR, &x);
    }
    GetTop(OPND, &c);
    return c;
}

void main(){
    int c;
    printf("Please input one expression:");
    c=EvaluateExpression();
    printf("Result=%d\n",c);
    getch();
}

欢迎登陆我的网站：

http://www.zblog.us/programing/cc/expression-stack.html | 赵杰的博客

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/148439.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权正版激活】： 官方授权正版激活支持Jetbrains家族下所有IDE 使用个人JB账号...