[栈](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);
}
其余操作均为做什么修改,具体修改的是主要功能函数下的操作数入栈步骤,代码如下:
这儿我起了两个临时变量,如果扫描到的是操作数 ,则进入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));
}
操作结果:
花了两天时间我还是没有想到如何通过一个栈实现。
字符数组我也试过了,整型数组我也试过了,结构我也试过了,但是都卡在了如何将计算好的数转换成字符串再次压入栈中,请求大佬解惑!