数据结构C语言—算术表达式求值[栈|中缀表达式法](采用双顺序栈实现)

目录

【TDTX】
【C99】
【编译与运行环境】64位Windows操作系统,TDM-gcc 4.9.2 64bit编译。
【输入样例】36.8+69-14.5(25.7-(45.4/2))-3.9#
【注2】采用中缀表达式法,符合人的直觉。
【注2】采用**float atof(const char
str);函数将数字字符串转为对应的float型的值,再压入OPND栈中。即实现了多位整数和浮点数表达式的计算**。
【问题描述】算术表达式求值问题。
【思路】
1.表达式求值问题中核心问题是实现算符的优先级,使用两个顺序栈分别作为操作数栈和运算符栈的运行工作栈,分别名为: OPND、OPTR。
2.两工作栈的栈底设定为数组 0 位置,栈顶设定为栈顶元素的下一个顺序位置。
【算法思想】
1.首先初始化两个工作栈,其中 OPTR 栈的栈底元素是#,即初始化后立即将#入栈到 OPTR 栈。
2. 依次读入表达式中的字符,是数字字符,将其转化为对应float,当读入到算符字符时先将此float入栈OPND
3. 若是运算符将 OPTR 栈顶的运算符与当前读入的运算符比较优先级后再执行相应的操作。其中栈顶元素优先级小于读入运算符,将该运算符入栈。
4. 若栈顶元素优先级大于读入运算符,将 OPTR 栈顶元素出栈保存在 theta 中,再让 OPND 出栈两次保存在 a 和 b 中,调用 Operate 函数执行算术运算,结果压入 OPND 中。

一、SbqzDouble.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define InitSize 100
#define StepSize 10
#define id_opnd 1
#define id_optr 2
char OP[7] = {'+','-','*','/','(',')','#'};
char tnumber[100];//保存表达式中的数字字符串,用atof函数转为float压入OPND
typedef struct SqStack_OPND
{
double* base;
double* top;
int stacksize;
int id;
}SqStack_OPND;
typedef struct SqStack_OPTR
{
char* base;
char* top;
int stacksize;
int id;
}SqStack_OPTR;
int InOP(char* OP,char c)
{
for(int i = 0;i < 7;i++)
{
if(c == OP[i])
{
return 1;
}
}
return 0;
} 
int initStack_OPND(SqStack_OPND* S)
{
S->base = (double*)malloc(sizeof(double)*InitSize);
if(S->base == NULL)
{
S->base = NULL;
S->top = NULL;
S->stacksize = -1;
return 0;
}
S->top = S->base;
S->stacksize = InitSize;
S->id = id_opnd;
return 1;
}
int initStack_OPTR(SqStack_OPTR* S)
{
S->base = (char*)malloc(sizeof(char)*InitSize);
if(S->base == NULL)
{
S->base = NULL;
S->top = NULL;
S->stacksize = -1;
return 0;
}
S->top = S->base;
S->stacksize = InitSize;
S->id = id_optr;
return 1;
}
int StackLength(void* s,int id)
{
if(id == id_opnd)
{
SqStack_OPND* S = (SqStack_OPND*)s;
if(S->base == NULL)
{
return -1;
}
return S->top-S->base;
}
if(id == id_optr)
{
SqStack_OPTR* S = (SqStack_OPTR*)s;
if(S->base == NULL)
{
return -1;
}
return S->top-S->base;
}
return -1;
}
int PushStack_OPND(SqStack_OPND* S,double e)
{
if(S->base == NULL)
{
puts("\nOPND is not exist!");
return 0;
}
if(StackLength(S,S->id) >= S->stacksize)
{
S->base = (double*)realloc(S->base,sizeof(double)*(S->stacksize+StepSize));
if(S->base != NULL)
{
S->top = S->base+S->stacksize;
S->stacksize = S->stacksize+StepSize;
*(S->top) = e;
(S->top)++;
return 1;
}
else
{
return 0;
}
}
else
{
*(S->top) = e;
(S->top)++;
return 1;
}
}
int PushStack_OPTR(SqStack_OPTR* S,char e)
{
if(S->base == NULL)
{
puts("\nOPND is not exist!");
return 0;
}
if(StackLength(S,S->id) >= S->stacksize)
{
S->base = (char*)realloc(S->base,sizeof(char)*(S->stacksize+StepSize));
if(S->base != NULL)
{
S->top = S->base+S->stacksize;
S->stacksize = S->stacksize+StepSize;
*(S->top) = e;
(S->top)++;
return 1;
}
else
{
return 0;
}
}
else
{
*(S->top) = e;
(S->top)++;
return 1;
}
}
int PopStack_OPND(SqStack_OPND* S,double* e)
{
if(S->base == NULL)
{
return -1;
}
if(S->base == S->top)
{
return 0;
}
else
{
(S->top)--;
*e = *(S->top);
return 1;
}
}
int PopStack_OPTR(SqStack_OPTR* S,char* e)
{
if(S->base == NULL)
{
return -1;
}
if(S->base == S->top)
{
return 0;
}
else
{
(S->top)--;
*e = *(S->top);
return 1;
}
}
int GetTopStack_OPND(SqStack_OPND* S,double* e)
{
if(S->base == NULL)
{
return -1;
}
if(S->base == S->top)
{
return 0;
}
else
{
*e = *(S->top - 1);
return 1;
}
}
int GetTopStack_OPTR(SqStack_OPTR* S,char* e)
{
if(S->base == NULL)
{
return -1;
}
if(S->base == S->top)
{
return 0;
}
else
{
*e = *(S->top - 1);
//printf("*e = %c",*e);
return 1;
}
}
int TraverseStack_OPND(SqStack_OPND* S)
{
if(S->base == NULL)
{
return -1;
}
if(S->base == S->top)
{
printf("栈顶指针----->0:空<-----栈底指针"); 
return 0;
}
double* p;
printf("栈顶指针----->%d\n",StackLength(S,S->id)); 
for(p = S->top;p - S->base - 1 != -1;p--)
{
if((p - S->base - 1) == 0)
{
printf("栈底指针----->0:%f\n",(S->base)[0]);
}
else
{
printf("              %d:%f\n",p - S->base - 1,(S->base)[p - S->base - 1]);
}
}
return 1;
}
int TraverseStack_OPTR(SqStack_OPTR* S)
{
if(S->base == NULL)
{
return -1;
}
if(S->base == S->top)
{
printf("栈顶指针----->0:空<-----栈底指针"); 
return 0;
}
char* p;
printf("栈顶指针----->%d\n",StackLength(S,S->id)); 
for(p = S->top;p - S->base - 1 != -1;p--)
{
if((p - S->base - 1) == 0)
{
printf("栈底指针----->0:%c\n",(S->base)[0]);
}
else
{
printf("              %d:%c\n",p - S->base - 1,(S->base)[p - S->base - 1]);
}
}
return 1;
}
double Operate(double a,char op,double b)
{
switch(op)
{
case '+':return a + b;
case '-':return a - b;
case '*':return a*b;
case '/':
if(fabs(b-0) <= 0.0000001)
{
return -2147483648.2147;
}
else
{
return a/b; 
}
default:return -2147483648.2147;
}
}
char Precede(char t1,char t2)
{
switch(t1)
{
case '+':
switch(t2)
{
case '+':return '>';
case '-':return '>';
case '*':return '<';
case '/':return '<';
case '(':return '<';
case ')':return '>';
case '#':return '>';
}
case '-':
switch(t2)
{
case '+':return '>';
case '-':return '>';
case '*':return '<';
case '/':return '<';
case '(':return '<';
case ')':return '>';
case '#':return '>';
}
case '*':
switch(t2)
{
case '+':return '>';
case '-':return '>';
case '*':return '>';
case '/':return '>';
case '(':return '<';
case ')':return '>';
case '#':return '>';
}
case '/':
switch(t2)
{
case '+':return '>';
case '-':return '>';
case '*':return '>';
case '/':return '>';
case '(':return '<';
case ')':return '>';
case '#':return '>';
}
case '(':
switch(t2)
{
case '+':return '<';
case '-':return '<';
case '*':return '<';
case '/':return '<';
case '(':return '<';
case ')':return '=';
case '#':return '@';
}
case ')':
switch(t2)
{
case '+':return '>';
case '-':return '>';
case '*':return '>';
case '/':return '>';
case '(':return '@';
case ')':return '>';
case '#':return '>';
}
case '#':
switch(t2)
{
case '+':return '<';
case '-':return '<';
case '*':return '<';
case '/':return '<';
case '(':return '<';
case ')':return '@';
case '#':return '=';
}
default:return '@';
}
}
double EvaluateExpression()
{
SqStack_OPND opnd;
SqStack_OPTR optr;
int n[1] = {0};
int k = 0;
char ch;
char c;
double pop_a;
double pop_b;
char theta;
char pop_ch;
double pop_return;
initStack_OPTR(&optr);PushStack_OPTR(&optr,'#');
initStack_OPND(&opnd);scanf("%c",&c);
while(c != '#' || (GetTopStack_OPTR(&optr,&ch),ch != '#'))  
{
if(InOP(OP,c) == 0)
{
if((c >= '0' && c <= '9') || c == '.')
{
n[0] = 0;
tnumber[k++] = c;
}
//printf("n[0] = %d,n[1] = %d,i-1 = %d\n",n[0],n[1],i-1);
//PushStack_OPND(&opnd,c-48);
//TraverseStack_OPND(&opnd);
//TraverseStack_OPTR(&optr);
//puts("-------------------");
c = getchar();
}
else
{
//printf("[c = %c,n[0] = %d]",c,n[0]);
if(n[0] == 0)
{
tnumber[k] = '\0';
//PushStack_OPND(&opnd,n[1]);
PushStack_OPND(&opnd,atof(tnumber));
n[0] = 1;
k = 0;
TraverseStack_OPND(&opnd);
TraverseStack_OPTR(&optr);
}
GetTopStack_OPTR(&optr,&ch);
switch(Precede(ch,c))
{
case '<':
PushStack_OPTR(&optr,c);
TraverseStack_OPND(&opnd);
TraverseStack_OPTR(&optr);
puts("-------------------");
c = getchar();
break;
case '=':
PopStack_OPTR(&optr,&pop_ch);
TraverseStack_OPND(&opnd);
TraverseStack_OPTR(&optr);
puts("-------------------");
c = getchar();
break;
case '>':
PopStack_OPTR(&optr,&theta);
PopStack_OPND(&opnd,&pop_a);
PopStack_OPND(&opnd,&pop_b);
if(Operate(pop_b,theta,pop_a) == -2147483648.2147)
{
return -2147483648.2147;
}
PushStack_OPND(&opnd,Operate(pop_b,theta,pop_a));
TraverseStack_OPND(&opnd);
TraverseStack_OPTR(&optr);
puts("-------------------");
break; 
}
}
}
GetTopStack_OPND(&opnd,&pop_return);
free(opnd.base);
free(optr.base);
return pop_return;
}
int main()
{
puts("【输入表达式以#结尾】其中运算符['+','-','*','/','(',')','#']:");
puts("【参与运算的数字只能是整数或浮点数】"); 
puts("【例子】:36+69-14*(25-(45/2))-3#"); 
printf("计算结果:%f\n",EvaluateExpression());
system("pause");
return 0;
}

二、EvaluateExpression()流程图

在这里插入图片描述

三、 函数模块清单

(1)int InOP(char* OP,char c);
(2)initStack_OPND(SqStack_OPND* S);
(3)initStack_OPTR(SqStack_OPTR* S);
(4)int StackLength(void* s,int id);
(5)int PushStack_OPND(SqStack_OPND* S,double e);
(6)int PushStack_OPTR(SqStack_OPTR* S,char e);
(7) int PopStack_OPND(SqStack_OPND* S,double* e);
(8) int PopStack_OPTR(SqStack_OPTR* S,char* e);
(9) int GetTopStack_OPND(SqStack_OPND* S,double* e);
(10) int GetTopStack_OPTR(SqStack_OPTR* S,char* e);
(11) int TraverseStack_OPND(SqStack_OPND* S);
(12) int TraverseStack_OPTR(SqStack_OPTR* S);
(13) double Operate(double a,char op,double b);
(14) char Precede(char t1,char t2);
(15) double EvaluateExpression();

三、 运行结果示例

3.1 36.8+69-14.5*(25.7-(45.4/2))-3.9#

在这里插入图片描述

3.2 36+69-14*(25-(45/2))-3#

在这里插入图片描述

3.3 动态图形式展示结果

在这里插入图片描述


------------------------------------------------------第九次发文章有点激动啊!-----------------------------------------------------
-----------------------------------------------------【数据结构代码自编练习】------------------------------------------------------
----------------------------------------------------------------【TDTX】-----------------------------------------------------------------

推荐这些文章:

C语言数据结构_栈的操作

入栈操作
入栈操作又叫压栈操作,就是向栈中存放数据。入栈操作要在栈顶进行,每向栈中压入一个数据,top指针就增加1,直到栈满为止。
#define STACKINCREMENT 10

Push(sqStack *s, ElemType e){
if(s->top - s->base >= s->stac...

数据结构--栈(C语言实现)

一、栈的基本概念
1.栈的定义
栈是一种只能在一端进行插入或删除的线性表。其中允许进行插入或删除操作的一端称为栈顶(top)。栈的插入和删除操作一般称作入栈和出栈。
2.栈的特点
先进后出
3.栈的存储结构
顺序栈和链式栈
注意:链式栈通常采用单链表实现,并规定所有的操作都是在单链表的表头进行的。而且对于带头结点和不带头结点的链栈,具体...

C语言数据结构_栈的定义以及如何创建一个栈

栈的定义
1、栈是一种重要的线性结构
2、栈(stack)是一个后进先出(LIFO)的线性表,要求只在表尾进行删除和插入等操作
//定义
typedef struct{
ElemType *base;
ElemType *top;
int stacksize;
}sqStack;

包含三个数据项:base、to...

考研C语言数据结构-顺序栈(栈的顺序存储实现)

#include <stdio.h>
#include <stdlib.h>

#define maxSize 6

// 定义顺序栈数据类型
typedef struct {

int data[maxSize];
int top;
}SqStack;

void initSqStack(SqStack &...

数据结构学习(二)栈


出栈顺序:由大变小按顺序,由小变大可突变

C++指针特性测试
#include <iostream>
using namespace std;
int main(){
int *p=new int[10];
for(int i=0;i<10;i++){
p[i]=0;
}...

数据结构学习2

1.顺序表插入
void InsertList(Sqlist &L,int i,ElemType x){
for ( int j=L.length-1;j>= i-1;--j )
L.elem[j+1]=L.elem[j];
L.elem[i-1]=x;
++L.length;
}...

考研C语言数据结构-顺序表(线性表的顺序存储实现)

#include <stdio.h>
#include <stdlib.h>

#define maxSize 10

// 定义顺序表存储结构数据类型
typedef struct {

int data[maxSize];
int length;
}SqList;

// 初始化顺序表
void init...

C语言数据结构_栈的实例分析

利用栈的数据结构,将二进制数转换为十进制数。
由于栈具有后进先出的特性,因此可以用栈很方便地实现二进制转换为十进制。
#include "stdio.h"
#include "math.h"
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10

typedef char ElemTy...

数据结构 栈的顺序和链式结构 C++实现

顺序存储结构的栈
栈的定义
const int MAXSIZE = 50;
typedef int Elemtype;
typedef struct
{
Elemtype data[MAXSIZE];
int top;
} SqStack;

栈的初始化

令栈顶指针 top 为 -1 即可;

void InitSta...

数据结构实验三

南昌航空大学实验报告
二0 21  年   5月 10  日
 
课程名称:     数据结构实验       实验名称:   ...

文章标题:数据结构C语言—算术表达式求值[栈|中缀表达式法](采用双顺序栈实现)
文章链接:https://www.dianjilingqu.com/4682.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>