[栈](4.2)支持浮点数的表达式求值

在这之前,我们已经通过栈的操作了解了逆波兰表达式求值的方法

但是之前的代码因为是用的int类型的栈,发现只能存储整数,而无法存储小数部分。

我试了很多办法,想使用一个栈搞定,但是字符数组转整型或浮点型容易,反过来反而特别麻烦 ,我试过用一个结构去存储输入的字符,分为主次两部分,但是后边还是特麻烦

所幸就不想了,直接起两个栈,方便易懂。

首先还是定义栈的结构,我起了一个算符栈,为char类型 ,其了一个操作数栈,为double类型,其余操作与之前差不多,只是多了一个字符转操作数的功能。

只是由于有两个不同结构的栈,需要起的函数也很多,两个栈分别都需要出栈入栈。

定义如下:

typedef struct
{
    char* base;
    char* top;
}SqStackR;
SqStackR OPTR;//算符栈


typedef struct
{
    double* base;
    double* top;
}SqStackN;
SqStackN OPND;//操作数栈

出栈入栈函数如下:

void InitStackR(SqStackR* S)//算符栈分配空间
{
    S->base = (char*)malloc(sizeof(char) * 100);
    S->top = S->base;
}

void InitStackN(SqStackN* S)//操作数栈分配空间
{
    S->base = (double*)malloc(sizeof(double) * 100);
    S->top = S->base;
}

void PushR(SqStackR* S, char a)//算符栈压入
{
    *(S->top) = a;
    S->top++;
}

void PushN(SqStackN* S, double a)//操作数栈压入
{
    *(S->top) = a;
    S->top++;
}

void PopR(SqStackR* S, char* a)//算符栈弹出
{
    S->top--;
    *a = *(S->top);
}

void PopN(SqStackN* S, double* a)//操作数栈弹出
{
    S->top--;
    *a = *(S->top);
}

其余操作均为做什么修改,具体修改的是主要功能函数下的操作数入栈步骤,代码如下:

img

这儿我起了两个临时变量,如果扫描到的是操作数 ,则进入if语块,逐次扫描直到扫到小数点的时候,再将小数点后的数保存起来。

同时计算小数点后扫描的次数,用一个变量保存起来,最后让小数点后的数除以它的进位,与小数点前的数相加再进栈

其余操作并无修改,完整算法如下:

#define STACKSIZE 100
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef struct
{
    char* base;
    char* top;
}SqStackR;
SqStackR OPTR;//算符栈


typedef struct
{
    double* base;
    double* top;
}SqStackN;
SqStackN OPND;//操作数栈

void InitStackR(SqStackR* S)//算符栈分配空间
{
    S->base = (char*)malloc(sizeof(char) * 100);
    S->top = S->base;
}

void InitStackN(SqStackN* S)//操作数栈分配空间
{
    S->base = (double*)malloc(sizeof(double) * 100);
    S->top = S->base;
}

void PushR(SqStackR* S, char a)//算符栈压入
{
    *(S->top) = a;
    S->top++;
}

void PushN(SqStackN* S, double a)//操作数栈压入
{
    *(S->top) = a;
    S->top++;
}

void PopR(SqStackR* S, char* a)//算符栈弹出
{
    S->top--;
    *a = *(S->top);
}

void PopN(SqStackN* S, double* a)//操作数栈弹出
{
    S->top--;
    *a = *(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(SqStackR S)//观察算符栈栈顶元素
{
    char a;
    a = *(S.top - 1);
    return a;
}

double Operate(double a, char b, double 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(char ch, char OP[])
{
    int p = 0;
    while (p < 7)
    {
        if (ch == OP[p])
        {
            return 1;
        }
        p++;
    }
    return 0;
}

int main()//EvaluateExpression()//操作函数
{
    char ch, theta, x;
    //   读入 算符  临时
    double b, d;
    //    左  右 
    ch = getchar();
    InitStackR(&OPTR);//为两栈分配空间
    InitStackN(&OPND);

    char OP[7] = { '+','-','*','/','(',')','#' };//定义集合
    PushR(&OPTR, '#');//算符栈压入
    while (ch != '#' || GetTop(OPTR) != '#')
    {
        if (!In(ch, OP))//判断是否为算符
        {
            int i = 1;//小数后控制变量
            double temp = 0.0;
            double temp2 = 0.0;//临时变量
            while (ch >= '0' && ch <= '9')
            {
                temp = temp * 10 + (ch - '0');
                ch = getchar();
            }
            if (ch == '.')
            {
                ch = getchar();
                while (ch >= '0' && ch <= '9')
                {
                    temp2 = temp2 * 10 + (ch - '0');
                    ch = getchar();
                    i = i * 10;
                }
            }
            temp = temp + temp2 / i;
            PushN(&OPND, temp);
        }
        else
        {
            switch (Precede(GetTop(OPTR), ch))
            {
            case'<':
                PushR(&OPTR, ch);
                ch = getchar();
                break;
            case'=':
                PopR(&OPTR, &x);
                ch = getchar();
                break;
            case'>':
                PopR(&OPTR, &theta);
                PopN(&OPND, &b);
                PopN(&OPND, &d);
                PushN(&OPND, Operate(d, theta, b));
                break;
            }
        }
    }
    printf("%lf", *(OPND.top - 1));
}

操作结果:

img

花了两天时间我还是没有想到如何通过一个栈实现。

字符数组我也试过了,整型数组我也试过了,结构我也试过了,但是都卡在了如何将计算好的数转换成字符串再次压入栈中,请求大佬解惑!

本文链接:

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