C语言-用栈实现表达式求值

这篇具有很好参考价值的文章主要介绍了C语言-用栈实现表达式求值。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

目的描述:

算法的基本思想:

错误点:

完整代码:

1.输入输出

2.栈操作函数包(数组堆栈.h)

3.实现表达式求值函数包(表达式求值.c)

4.测试输出:


目的描述:

算符优先算法要实现的是,根据运算优先关系来对一个表达式求值,假如说要计算:

4+2*3-10/5

运算的顺序例如:

4+2*3-10/5  =  4+6-10/5  =  10-10/5  =  10-2  =  8 (开始不是很理解的话可以继续往下看)

算法的基本思想:

为实现算符优先算法,可以使用两个工作栈。一个称做 OPTR,用以寄存运算符;另一个称做 OPND,用以寄存操作数或运算结果。

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

(3)在这里分别定义了两套对栈进行基本操作的函数,只有函数名改变其他均相同。这样做的原因是,在对寄存运算符时,需要字符栈;而寄存操作数或运算结果时,字符栈无法满足多位数的操作,所以这里采用数字栈(后来看到了另一位作者的文章,两个栈都采用数字栈也可以实现,并且会大大减少代码数量,原理就是在存放操作符的时候,将会转化成ASCII码的形式存入栈中)

(4)这里是两个最近的运算符的优先级关系表:(用来参考着写计算算符优先级的函数)

C语言-用栈实现表达式求值

 (空白的地方是不可能存在的合法运算符关系,可忽略)

(5)通过利用对栈的基本操作函数,对两个栈进行操作,按步骤分解可以参考下表

 C语言-用栈实现表达式求值

错误点:

(记录一下自己遇到的错误)

(1)就是关于在寄存操作数或运算结果时开始没有考虑到有多位数的情况,我对多位数的处理是,设定了一个flag判断,如果连续getchar()得到的都是数字,就令flag=1;如果遇到了运算符,就令flag=0。

(2)在计算每一步结果的函数 Operate(double a, char theta, double b)里,当这是的操作是’-‘或者’/‘时,要注意a,b的顺序,因为栈的特点是LIFO(last in first out),所以除数和被除数,减数和被减数就会颠倒过来,要记得写成反的。

(3)记得判断输入getchar()为换行符’\n'时要跳出循环的判断。

完整代码:

1.输入输出

输入:一个只含有‘+’,‘-’,‘/’,‘*’,‘#’运算符和数字的运算表达式,中间没有空格,结尾以#结束

输出:一个整数计算结果

2.栈操作函数包(数组堆栈.h)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char Elemtype1;//提供给存储运算符的栈使用
typedef double Elemtype2;//提供给存储操作数的栈使用

typedef struct {
	Elemtype1 *data;
	int top;//栈顶指针,这里用int类型表示指针的下标
	int stacksize;
} SqStack1;
Elemtype1 Pop1(SqStack1 *s);

typedef struct {
	Elemtype2 *data;
	int top;//栈顶指针,这里用int类型表示指针的下标
	int stacksize;
} SqStack2;
Elemtype2 Pop2(SqStack2 *s);

SqStack1 InitStack1() {//空栈构造函数
	SqStack1 s;
	s.data = (Elemtype1 *)malloc(STACK_INIT_SIZE * sizeof(Elemtype1));
	s.top = -1; //表示栈空
	s.stacksize = STACK_INIT_SIZE;
	if (s.data != NULL)
	{}
	else
		printf("Init error!\n");
	return s;
}

void DestroyStack1(SqStack1 *s) {//销毁栈函数
	free(s->data);
}

int StackEmpty1(SqStack1 *s) {//判断是否为空栈,是返回1,否 返回0
	if (s->top == -1)
		return 1;
	else
		return 0;
}

void ClearStack1(SqStack1 *s) {//清除栈
	while (StackEmpty1(s) != 1) {
		Pop1(s);
	}
}

void Push1(SqStack1 *s, Elemtype1 e) {//添加元素入栈
	if (s->top >= s->stacksize) {
		s->data = (Elemtype1 *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(Elemtype1));
		s->stacksize += STACKINCREMENT;
		if (s->data != NULL) {}
		else
			printf("Push error!\n");
	} else {
		s->top++;
		s->data[s->top] = e;
	}
}

Elemtype1 Pop1(SqStack1 *s) {//删除栈顶元素并返回其值,否则返回ERROR
	if (StackEmpty1(s) != 1 && s->top >= 0) {
		Elemtype1 e = s->data[s->top];
		s->top--;
		return e;
	}
	printf("Pop error!\n");
}

int StackLength1(SqStack1 *s) {//返回栈的长度
	int len = 0, temp = s->top;
	while (temp >= 0) {
		len++;
		temp--;
	}
	return len;
}

Elemtype1 GetTop1(SqStack1 *s) {//返回栈顶元素
	if (StackEmpty1(s) != 1) {
		return s->data[s->top];
	} else
		printf("GetTop error!\n");
}

int StackTraverse1(SqStack1 *s) {//从栈底向栈顶访问每个元素
	if (StackEmpty1(s) == 1) {
		printf("栈为空!\n");
		return 0;
	}
	int temp = 0;
	while (temp <= s->top) {
		printf("%c ", s->data[temp]);
		temp++;
	}
	return 1;
}

//以下是对第二组堆栈操作的定义*************************************************
SqStack2 InitStack2() {//空栈构造函数
	SqStack2 s;
	s.data = (Elemtype2 *)malloc(STACK_INIT_SIZE * sizeof(Elemtype2));
	s.top = -1; //表示栈空
	s.stacksize = STACK_INIT_SIZE;
	if (s.data != NULL)
	{}
	else
		printf("Init error!\n");
	return s;
}

void DestroyStack2(SqStack2 *s) {//销毁栈函数
	free(s->data);
}

int StackEmpty2(SqStack2 *s) {//判断是否为空栈,是返回1,否 返回0
	if (s->top == -1)
		return 1;
	else
		return 0;
}

void ClearStack2(SqStack2 *s) {//清除栈
	while (StackEmpty2(s) != 1) {
		Pop2(s);
	}
}

void Push2(SqStack2 *s, Elemtype2 e) {//添加元素入栈
	if (s->top >= s->stacksize) {
		s->data = (Elemtype2 *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(Elemtype2));
		s->stacksize += STACKINCREMENT;
		if (s->data != NULL) {}
		else
			printf("Push error!\n");
	} else {
		s->top++;
		s->data[s->top] = e;
	}
}

Elemtype2 Pop2(SqStack2 *s) {//删除栈顶元素并返回其值,否则返回ERROR
	if (StackEmpty2(s) != 1 && s->top >= 0) {
		Elemtype2 e = s->data[s->top];
		s->top--;
		return e;
	}
	printf("Pop error!\n");
}

int StackLength2(SqStack2 *s) {//返回栈的长度
	int len = 0, temp = s->top;
	while (temp >= 0) {
		len++;
		temp--;
	}
	return len;
}

Elemtype2 GetTop2(SqStack2 *s) {//返回栈顶元素
	if (StackEmpty2(s) != 1) {
		return s->data[s->top];
	} else
		printf("GetTop error!\n");
}

int StackTraverse2(SqStack2 *s) {//从栈底向栈顶访问每个元素
	if (StackEmpty2(s) == 1) {
		printf("栈为空!\n");
		return 0;
	}
	int temp = 0;
	while (temp <= s->top) {
		printf("%c ", s->data[temp]);
		temp++;
	}
	return 1;
}

3.实现表达式求值函数包(表达式求值.c)

#include "数组堆栈.h"
double EvaluateExpression();
int isAccepted(char);
char Precede(char, char);
double Operate(double a, char theta, double b);

int main() {
	printf("请输入一个表达式:");
	double result;
	result = EvaluateExpression();
	printf("表达式的计算结果是:%0.f", result);
	return 0;
}

int flag = 0; //如果在操作数栈有连续数字的输入,则设flag=1标记,用于多位数的计算
double EvaluateExpression() {
	SqStack1 OPTR;
	SqStack2 OPND;
	char e, theta;
	double a, b;
	e = getchar();
	OPTR = InitStack1(); //运算符栈
	Push1(&OPTR, '#');
	OPND = InitStack2(); //操作数或运算结果栈
	while (GetTop1(&OPTR) != '#' || e != '#') {
		if (e == '\n')
			break;
		if (isAccepted(e) == 1) { //如果字符是数字
			e = e - '0';
			if (flag == 1) { //是多位数
				double temp = Pop2(&OPND);
				temp = temp * 10 + e;
				Push2(&OPND, temp);
			} else {
				Push2(&OPND, e);
				flag = 1;
			}
			e = getchar();
		} else {
			flag = 0;
			switch (Precede(GetTop1(&OPTR), e)) {
				case '<'://栈顶元素优先级低,压入栈
					Push1(&OPTR, e);
					e = getchar();
					break;
				case '>'://新运算符优先级低,将前一个运算符弹出进行计算
					a = Pop2(&OPND);
					theta = Pop1(&OPTR);
					b = Pop2(&OPND); //abc
					//将计算结果再次压入运算结果栈
					Push2(&OPND, Operate(a, theta, b));
					//注意这里不用再重新获取e的值
					break;
				case '=':
					Pop1(&OPTR);//将剩下的一半括号弹出
					e = getchar();
					break;
			}
		}
	}
	return GetTop2(&OPND);//返回计算结果

}

int isAccepted(char e) { //如果字符是数字,返回1;字符是运算符,返回2;否则返回0
	char number[15] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
	char calculate[15] = {'+', '-', '(', ')', '*', '#', '/'};
	for (int i = 0; i <= 9; i++) {
		if (number[i] == e)
			return 1;
	}
	for (int i = 0; i <= 6; i++) {
		if (calculate[i] == e)
			return 2;
	}
	return 0;
}

char Precede(char a, char b) {
	if (b == '+' || b == '-') {
		if (a == '(' || a == '#')
			return '<';
		else
			return '>';
	} else if (b == '*' || b == '/') {
		if (a == '*' || a == '/' || a == ')')
			return '>';
		else
			return '<';
	} else if (b == '(')
		return '<';
	else if (b == ')') {
		if (a != '(')
			return '>';
		else
			return '=';
	} else if (b == '#') {
		if (a != '#')
			return '>';
		else
			return '=';
	}

}

double Operate(double a, char theta, double b) {
	if (b == 0) {
		printf("Conflicts with calculation rules!\n");
		return;
	}
	if (theta == '+')
		return a + b;
	else if (theta == '-')
		return b - a;//因为栈先弹出减数,所以要交换顺序
	else if (theta == '*')
		return a * b;
	else if (theta == '/')
		return b / a;//因为栈先弹出除数,所以要交换顺序
}

4.测试输出:

C语言-用栈实现表达式求值

有错误欢迎指正喔!!\\(^-^)//文章来源地址https://www.toymoban.com/news/detail-409526.html

到了这里,关于C语言-用栈实现表达式求值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C语言】表达式求值中类型转换和优先级

    目录 1.隐式类型转换 2.算数转换 ​3.操作符的属性 C的整型算术运算总是至少以缺省整型类型的精度来进行的。 为了获得这个精度,表达式中的字符和短整型操作数在使用之前被转换为普通整型,这种转换称为 整型提升 。 整型提升的意义: 表达式的整型运算要在CPU的相应运

    2024年02月13日
    浏览(40)
  • 初始C语言(6)——详细讲解表达式求值以及其易错点

     第一章 “C“浒传——初识C语言(1)(更适合初学者体质哦!)  第二章 初始C语言(2)——详细认识分支语句和循环语句以及他们的易错点   第三章 初阶C语言(3)——特别详细地介绍函数  第四章 初始C语言(4)——详细地讲解数组的内容以及易错点  第五章 初

    2024年02月12日
    浏览(37)
  • C语言——表达式求值中类型转换和优先级等问题

    目录 1.隐式类型转换 2.算数转换 ​3.操作符的属性 C的整型算术运算总是至少以缺省整型类型的精度来进行的。 为了获得这个精度,表达式中的字符和短整型操作数在使用之前被转换为普通整型,这种转换称为 整型提升 。 整型提升的意义: 表达式的整型运算要在CPU的相应运

    2024年02月05日
    浏览(83)
  • 表达式求值问题-双栈模板化实现

            好久不见,真的很久都没有更新博客了,最近很多事情,所以比较忙碌,没有时间每天都学算法,但是我会挤时间尽量做到,每两三天就更新博客,我会努力的,加油~     前言:计算器都见过吧,我们今天要讲的就是类似于计算器计算数据的简单实现,我们需要注

    2024年02月03日
    浏览(43)
  • 数据结构课程实验二:运用栈实现表达式求值

    目录 一、实验目的 二、实验内容 三、实验提示  四、实验思路

    2023年04月17日
    浏览(43)
  • 文本单词查询复合表达式求值的实现案例分析

            本文讨论的“ 文本单词查询复合表达式求值的实现 ”案例,来自C++ primer第四版,该案例面向对象编程和泛型编程, 涉及类的继承、抽象、多态、句柄、标准IO库、容器、算法库 ,是综合性很强的程序         该程序实现文本中查找单个单词,“非”查询(使

    2024年01月23日
    浏览(35)
  • 4.2 实现基于栈的表达式求值计算器(难度4/10)

    本作业主要考察:解释器模式的实现思想/栈结构在表达式求值方面的绝对优势 C++数据结构与算法夯实基础作业列表 通过栈的应用,理解特定领域设计的关键作用,给大家眼前一亮的感觉。深刻理解计算机语言和人类语言完美结合的杰作。是作业中的上等作品,是数据结构与

    2024年02月10日
    浏览(33)
  • 【C语言】表达式求值相关问题汇总—>隐式类型转换(整型提升)、算数转换与操作符优先级汇总(收藏查阅)

     👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》 🌝 每一个不曾起舞的日子,都是对生命的辜负。 目录 前言: 一、隐式类型转换 (一)整型提升的意义 (二)如何进行整型提升呢? 二、算数转换 三、操作符的属性 (一)操作符优先级汇

    2024年02月16日
    浏览(42)
  • c++表达式求值

    给定一个表达式,其中运算符仅包含 +,-, ,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。 注意: 数据保证给定的表达式合法。题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2) (-(1+1)+2) 之类表达式均不会出现。题目保表达式中所有数字均

    2024年01月21日
    浏览(36)
  • 表达式求值和转换

    2024年02月06日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包