[栈](1.1)表达式求值

338
[ 数据结构 ] [ 栈和队列 ]

算符优先法就是根据这个运算优先关系的规定来实现对表达式编译或解释执行的。

任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的，我们称它们为单词，一般的，操作数既可以是常数，也可以是被说明为变量或常量的标识符

运算符可以分为算术运算符、关系运算符和逻辑运算符3类，基本界限符有左右括号和表达式结束符等。

我们把运算符和界限符统称为算符，它们构成的集合命名为OP，根据上述3条运算规则，在运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面3种关系之一：

  • θ1<θ2 θ1的优先权低于θ2
  • θ1=θ2 θ1的优先权等于θ2
  • θ1>θ2 θ1的优先权高于θ2

如下图所示，定义了算符之间的这种优先关系

img

为实现算符优先算法，可以使用两个工作栈，一个称做OPTR，用以寄存运算符。

另一个称作OPND，用以寄存操作数或运算结果，算法的基本思想是：

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

算法如下：

Operand_EvaluateExpression()
//算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈
//OP为运算符集合
{
    InitStack(OPTR);
    Push(OPTR, '#');
    InitStack(OPND);
    c = getchar();

    while (c != '#' || GetTop(OPRT) != '#')
    {
        if (!In(c, OP))//不是运算符则进栈
        {
            Push((OPND, c));
            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, theta);
                Pop(OPND, b);
                Pop(OPND, a);
                Push(OPDN, Operate(a, theta, b));
                break;
            }
        }
        return GetTop(OPND);
    }
}

按题目要求，需要声明两个栈，一个OPTR，存储算符，一个OPND，存储操作数

定义如下：

typedef struct
{
    int* base;
    int* top;
}SqStack;
SqStack OPND,OPTR

利用int类型，存储操作数，和算符，对于算符，可利用ASCII码来代替：

二进制码 八进制码 十进制码 十六进制码 算符 说明
0010 1000 050 40 0x28 ( 开括号
0010 1001 051 41 0x29 ) 闭括号
0010 1010 052 42 0x2A * 星号
0010 1011 053 43 0x2B + 加号
0010 1101 055 45 0x2D - 减号/破折号
0010 1111 057 47 0x2F / 斜杠
0010 0011 043 35 0x23 # 井号

利用上述存储ASCII码，然后需要使用前转换成字符类型来代替

然后是构造一个结构体，这儿采用动态顺序表的存储结构，声明如下：

void InitStack(SqStack* S)
{
    S->base = (int*)malloc(sizeof(int) * STACKSIZE);
    if (S->base == NULL)
    {
        printf("Fail");
        exit(-1);
    }
    S->top = S->base;
}

然后最重要的两个函数：出栈和入栈，定义如下：

void Push(SqStack* S, int a)
{
    *(S->top) = a;
    if (S->top - S->base > S->stacksize)
    {
        printf("栈满\n");
        exit(0);
    }
    S->top++;
}
void Pop(SqStack* S, int* e)
{
    if (S->base == S->top)
    {
        printf("栈空\n");
        exit(0);
    }
    S->top--;
    *e = *(S->top);
}

然后我们需要构造一个比较函数，用于比较运算符的优先权，算法如下

char Precede(char a, char b)
{
    char op[][7] = { { '>','>','<','<','<','>','>' },
                     { '>','>','<','<','<','>','>' },
                     { '>','>','>','>','<','>','>' },
                     { '>','>','>','>','<','>','>' },
                     { '<','<','<','<','<','=','0' },
                     { '>','>','>','>','0','>','>' },
                     { '<','<','<','<','<','0','=' }, };
    int i, j;
    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;
    }
    ;

    if (op[i][j] == '0')
    {
        printf("表达式不合法\n");
        exit(-1);
    }
    return op[i][j];
}

然后我们需要定义一个查看函数，用来查看栈顶元素，这儿主要用到的是查看算符，则在函数内需要转换成字符来查看，算法如下：

char GetTop(SqStack S)
{
    char a =(int)*(S.top - 1);
    return a;
}
  • 这儿需要主要，观察需要转换成整型然后再转换成字符型，最后返回

然后我们需要定义一个判断函数，判断传入参数是否为算符，算法如下：

int In(int a,char OP[])
{
    char c = (char)a;
    int p = 0;
    while (p<7)
    {
        if (c == OP[p])
        {
            return 1;
        }
        p++;
    }
    return 0;
}

最后我们还需要一个计算函数，用来表达式求值

double Operate(int a, char b, int c)
{
    switch (b)
    {
    case'+':
        return a + c;
        break;
    case'-':
        return a - c;
        break;
    case'*':
        return a * c;
        break;
    case'/':
        return a / c;
        break;
    }
}

万事俱备，这时我们来编写核心函数

int EvaluateExpression()
{
    char a,theta;
    int b,d,c,x;
    a = getchar();
    InitStack(&OPTR);
    InitStack(&OPND);
    char OP[7] = { '+','-','*','/','(',')','#' };
    Push(&OPTR, '#');
    while (a != '#' || GetTop(OPTR) != '#')
    {
        if (!In(a, OP))
        {
            Push(&OPND, a-'0');
            a = getchar();
        }
        else
        {
            switch (Precede(GetTop(OPTR),a))
            {
            case'<':
                Push(&OPTR,a);
                a = getchar();
                break;
            case'=':
                Pop(&OPTR, &x);
                a = getchar();
                break;
            case'>':
                Pop(&OPTR, &c);
                theta = (char)c;
                Pop(&OPND, &b);
                Pop(&OPND, &d);
                Push(&OPND, Operate(d, theta, b));
                break;
            }
        }
    }
    printf("\n%d", *(OPND.top - 1));
}

这边需要注意的是，由于在栈内存储的都为int类型， 则算符入栈也会被转换为int类型。

但是getchar()函数是从缓冲区接收一个字符，则在操作数入栈的时候，需减去一个空字符，得到原有的数值

img这儿原理可以对照ASCII表

且在进行计算的时候，由于栈内都是整型数据，需要一个字符变量将其转化为字符型。

img这里的c为整型，用于接收栈内数据，theta为 字符型，用于转换

还需注意的是，由于栈是后进先出的结构，在计算是，出栈顺序也应该是从右到左！

img悄咪咪的说我在这儿卡了一会儿

运算结果：

img

此算法只能用于理解栈的运用，由于都是整数类型的栈，不能计算浮点数的结果，且因为getchar()的特性，只能单个字符的传入，比如输入10，它只会存储0，而不会存储10这个数值（点击进入支持浮点数的算法笔记）

  • 如需计算浮点数以及多位数，请查看补充笔记

下面拟主要操作过程：

img

当碰到算符优先权相等的时候，只有左括号匹配到右括号，这时需要的操作就是将左括号退栈，如代码所示

还需要注意的是，当输入的算符优先权大于栈顶的算符，需要将之前的结果计算出来并且入栈，这时不需要重新读入字符，这时还是保留着之前读入的字符，进行下一次的循环。

例如上图所示：

  • a首先读入的为3，存入OPND栈，进行下一次循环
  • a读入的为，进行判断，栈顶为#，小于，入OPTR栈，进行下一次循环
  • a读入的为(，进行判断，栈顶为*，小于(，入OPTR栈，进行下一次循环
  • a读入的为7，存入OPND栈，进行下一次循环
  • a读入的为-，进行判断，栈顶为(，小于-，如OPTR栈，进行下一次循环
  • a读入的为2，存入OPND栈，进行下一次循环
  • a读入的为）,进行判断，栈顶为-，大于），则取出栈中2和7，进行相减，得到结果5，存入OPND栈，此时栈从下到上为：3 5
  • a保持），继续进行下一次循环，遇到了（相等，则将（退栈，重新读入a
  • a读入为#，进行判断，栈顶为*，大于#，则取出栈中的5和3，进行相乘，得到结果为15，存入OPND栈
  • 此时循环条件都不满足，a保持读入#，而算符OPTR栈顶元素也为#，退出循环
  • 得到结果为15

这样就明了很多了，得到相等的结果可以理解成左括号遇到了右括号，则计算完括号中的数值，直到栈顶为左括号的时候，将它退栈，然后再进行下一次读入。

完整代码如下：

#define STACKSIZE 100
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int* base;
    int* top;
    int stacksize;
}SqStack;
SqStack OPND, OPTR;

void InitStack(SqStack* S)
{
    S->base = (int*)malloc(sizeof(int) * STACKSIZE);
    if (S->base == NULL)
    {
        printf("Fail");
        exit(-1);
    }
    S->top = S->base;
    S->stacksize = STACKSIZE;
}

void Push(SqStack* S, int a)
{
    *(S->top) = a;
    if (S->top - S->base > S->stacksize)
    {
        printf("栈满\n");
        exit(0);
    }
    S->top++;
}
void Pop(SqStack* S, int* e)
{
    if (S->base == S->top)
    {
        printf("栈空\n");
        exit(0);
    }
    S->top--;
    *e = *(S->top);
}
char Precede(char a, char b)
{
    char op[][7] = { { '>','>','<','<','<','>','>' },
                     { '>','>','<','<','<','>','>' },
                     { '>','>','>','>','<','>','>' },
                     { '>','>','>','>','<','>','>' },
                     { '<','<','<','<','<','=','0' },
                     { '>','>','>','>','0','>','>' },
                     { '<','<','<','<','<','0','=' }, };
    int i, j;
    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;
    }

    if (op[i][j] == '0')
    {
        printf("表达式不合法\n");
        exit(-1);
    }
    return op[i][j];
}

char GetTop(SqStack S)
{
    char a =(int)*(S.top - 1);
    return a;
}
int Operate(int a, char b, int c)
{
    switch (b)
    {
    case'+':
        return a + c;
        break;
    case'-':
        return a - c;
        break;
    case'*':
        return a * c;
        break;
    case'/':
        return a / c;
        break;
    }
}

int In(int a,char OP[])
{
    char c = (char)a;
    int p = 0;

    while (p < 7)
    {
        if (c == OP[p])
        {
            return 1;
        }
        p++;
    }
    return 0;
}

int main()//EvaluateExpression()
{
    char a,theta;
    int b,d,c,x;
    a = getchar();
    InitStack(&OPTR);
    InitStack(&OPND);
    char OP[7] = { '+','-','*','/','(',')','#' };
    Push(&OPTR, '#');
    while (a != '#' || GetTop(OPTR) != '#')
    {
        if (!In(a, OP))
        {
            Push(&OPND, a-'0');
            a = getchar();
        }
        else
        {
            switch (Precede(GetTop(OPTR),a))
            {
            case'<':
                Push(&OPTR,a);
                a = getchar();
                break;
            case'=':
                Pop(&OPTR, &x);
                a = getchar();
                break;
            case'>':
                Pop(&OPTR, &c);
                theta = (char)c;
                Pop(&OPND, &b);
                Pop(&OPND, &d);
                Push(&OPND, Operate(d, theta, b));
                break;
            }
        }
    }
    printf("\n%d", *(OPND.top - 1));
}

本文链接：

https://nullcode.fun/19.html
1 + 2 =
快来做第一个评论的人吧~