程序员经验分享-hwhale

C语言中缀表达式求值(综合)

2023-10-29

题前需要了解的：中缀、后缀表达式是什么？（不知道你们知不知道，反正我当时不知道，搜的百度）

在这里插入图片描述

基本思路:先把输入的中缀表达式→后缀表达式→进行计算得出结果
栈：”先进先出，先进后出“！

  1. 中缀转后缀（先把转换后的后缀表达式存入字符数组）：从左至右依次读取，遇到运算数存入字符数组，遇到运算符压入栈，继续读取–如果遇到的运算符优先级比栈顶的运算符优先级低或者相等（比如“+与+或-” ----- “* 与 或/”------“/与/或”），则先将栈中的运算符输送至字符数组（如果栈中有“（”，则只输出到左括号就停止输出，不输出左括号），继续读取–如果遇到运算符优先级比栈顶运算符高的则入栈成为新的栈顶运算符，继续读取----如果遇到“）”，则将栈元素输出至字符数组，直至输出至”（“停止（在后缀表达式中没有括号，所以括号不输出入字符数组），直至读取完毕，然后将栈中剩余的运算符输出至字符数组。完毕！（注意：在遇到右括号”）“后就要将”（“左括号从栈中删除了，因为为防止将括号输出至字符数组）。

  2. 后缀表达式求值：从左至右读取，遇到运算数则将其存入栈中，遇到运算符（比如”/“）则将栈顶元素的前一个运算数（比如temp1）与栈顶元素（比如temp2）出栈（–注意–）并进行运算，temp1/temp2，并将其最终结果重新压入栈中成为新的栈顶元素，直至得出最终结果。

上代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100  
typedef float Num;//为防止以后变换操作数类型需要 
typedef struct
{
	Num data[MAX];
	int top;
}StackNum;//运算数栈 
typedef struct
{
	char data[MAX];
	int top;
}StackChar;//运算符栈 
//------函数声明---------
void InitNum(StackNum *p);//运算数栈初始化 
void PushNum(StackNum *p, Num e);//运算数压栈 
void PopNum(StackNum *p, Num *e);//运算数出栈
Num GetNum(StackNum p);//取栈顶元素 
//-----------------------
void InitChar(StackChar *p);//运算符栈初始化
void PushChar(StackChar *p, char e);//运算符压栈 
void PopChar(StackChar *p, char *e);//运算符出栈 
//-----------------------
void Fun(StackNum *p, char e);//计算并压入运算数栈 
//-----------------------
void main()
{
	int i;//循环变量 
	Num temp;//存放一个临时转换数
	char str[MAX], ch;//存放中缀表达式原式，临时运算符 
	//-----------
	StackNum n1;
	StackChar c1;
	InitNum(&n1);
	InitChar(&c1);
	//------------
	
	for (;;)
	{
		printf("请输入中缀表达式：");
		gets(str);
		/*
		注意字符串输入函数与scanf("%s",str) 的区别，scanf遇到空白字符，
		包括空格，制表符，换行符时均会停止输入，所以不可取,而gets功能为读入一行，
		并将换行符转换为字符串结束符。
		*/
		for (i = 0; str[i] != '\0'; i++)//读完整字符串-----字符串结束标志'\0' 
		{
			if (str[i] >= '0'&&str[i] <= '9')//分岔点一：----------------------------------------------------------------如果为数字 
			{
				temp = str[i] - '0';//-----将字符转换为数值 


				while (str[i + 1] != '\0')//多位数值获取 
				{
					if (str[i + 1] >= '0'&&str[i + 1] <= '9')
					{
						temp = temp * 10 + str[i + 1] - '0';//------注意！ 

						i++;
					}
					else
						break;//如果不是多位数字，则跳出多位获取循环 
				}
				PushNum(&n1, temp);//将获取来的数值入栈 
			}
			else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')')//分岔点二：-------如果为运算符 
			{
				switch (str[i])//表达式可为：整型/字符型/枚举型-----C语言中 
				{
					//case 后可为 整型，字符型----C语言中 
				case '+':
					if (c1.data[c1.top - 1] != '+'&&c1.data[c1.top - 1] != '-'&&c1.data[c1.top - 1] != '*'&&c1.data[c1.top - 1] != '/')
					{
						PushChar(&c1, '+');
					}
					else//如果不然，则将之前的先都出栈并计算，然后再入栈
					{
						while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算，其中括号内的优先级最高 
						{
							PopChar(&c1, &ch);
							Fun(&n1, ch);//计算，并压运算数栈

						}
						PushChar(&c1,'+');
					}
					; break;
				case '-':
					if (c1.data[c1.top - 1] != '+'&&c1.data[c1.top - 1] != '-'&&c1.data[c1.top - 1] != '*'&&c1.data[c1.top - 1] != '/')
					{
						PushChar(&c1, '-');
					}
					else//如果不然，则将之前的先都出栈并计算，然后再入栈
					{
						while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算，其中括号内的优先级最高 
						{
							PopChar(&c1, &ch);
							Fun(&n1, ch);//计算，并压运算数栈

						}
						PushChar(&c1, '-');
					}
					; break;
				case '*':
					if (c1.data[c1.top - 1] != '*'&&c1.data[c1.top - 1] != '/')
					{
						PushChar(&c1, '*');
					}
					else//如果不然，则将之前的先都出栈并计算，然后再入栈
					{
						while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算，其中括号内的优先级最高 
						{
							PopChar(&c1, &ch);
							Fun(&n1, ch);//计算，并压运算数栈

						}
						PushChar(&c1, '*');
					}
					; break;
				case '/':
					if (c1.data[c1.top - 1] != '*'&&c1.data[c1.top - 1] != '/')
					{
						PushChar(&c1, '/');
					}
					else//如果不然，则将之前的先都出栈并计算，然后再入栈
					{
						while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算，其中括号内的优先级最高 
						{
							PopChar(&c1, &ch);
							Fun(&n1, ch);//计算，并压运算数栈

						}
						PushChar(&c1, '/');
					}
					; break;
				case '(':

					PushChar(&c1, '(');

					; break;
				case ')'://并没有将'('压入栈中，只是当作一种出栈信号 
					while (c1.data[c1.top - 1] != '(')
					{
						PopChar(&c1, &ch);
						Fun(&n1, ch);//计算，并压运算数栈
					}
					PopChar(&c1, &ch);//将'('也出栈，但并不计算 
					; break;
				}

			}
		}
		while (c1.top > 0)//将剩余的运算符出栈并计算 
		{
			PopChar(&c1, &ch);
			Fun(&n1, ch);
		}
		printf("\t\t%s=%.2f", str, GetNum(n1));
		printf("\n");
		system("pause");
	}
	
}
void InitNum(StackNum *p)
{
	p->top = 0;
}
void InitChar(StackChar *p)
{
	p->top = 0;
}
void PushNum(StackNum *p, Num e)
{
	if (p->top == MAX)
		printf("运算数栈满！\n");
	else
	{
		p->data[p->top] = e;
		p->top++;
	}
}
void PushChar(StackChar *p, char e)
{
	if (p->top == MAX)
		printf("运算符栈满！\n");
	else
	{
		p->data[p->top] = e;
		p->top++;
	}
}
void PopNum(StackNum *p, Num *e)
{
	if (p->top == 0)
		printf("运算数栈空！\n");
	else
	{
		p->top--;
		*e = p->data[p->top];
	}
}
void PopChar(StackChar *p, char *e)
{
	if (p->top == 0)
		printf("运算符栈空！\n");
	else
	{
		p->top--;
		*e = p->data[p->top];
	}
}
void Fun(StackNum *p, char e)
{
	Num temp1, temp2;//存放两个临时操作数 
	PopNum(p, &temp2);
	PopNum(p, &temp1);
	switch (e)
	{
	case '+':PushNum(p, temp1 + temp2); break;
	case '-':PushNum(p, temp1 - temp2); break;
	case '*':PushNum(p, temp1*temp2); break;
	case '/':PushNum(p, temp1 / temp2); break;

	}
}
Num GetNum(StackNum p)
{
	return p.data[p.top - 1];
}

因为我也是个小菜鸟，所以本次也全当作笔记总结的文章，我又找了两篇我参考的大佬的文章，如下：

原文：https://blog.csdn.net/myCsdn_Xm/article/details/80861183

后缀表达式的求值（c语言）

题目描述
为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为后缀{运算符在后，如X/Y写为XY/表达式。在这样的表示中可以不用括号即可确定求值的顺序，如：(P+Q)(R－S) → PQ+RS－。后缀表达式的处理过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。
输入
输入一行表示后缀表达式，数与数之间一定有空格隔开（可能不只一个空格），最后输入@表示输入结束。

数据保证每一步的计算结果均为不超过100000的整数。

输出
输出一个整数，表示该表达式的值.
样例输入
14 3 20 5 / *8 - + @
样例输出
18

#include<stdio.h>

typedef struct STRACK                                              //定义结构体
{
    double a[100];
    int top;
} STRACK;

int main()
{
    double totle=0,e=0;
    char s[100];
    int i;

    STRACK L;
    L.top=-1;
    gets(s);
    for(i=0; s[i]!='@'; i++)
    {
        if(s[i]<='9'&&s[i]>='0')
        {
            L.top++;
            int temp=s[i]-'0';
            int k=i+1;
            while(s[k]!='@')                                          //利用while循环得到由多位由字符组成的数值
            {
                if(s[k]<='9'&&s[k]>='0')
                {
                    temp=10*temp+(s[k]-'0');
                    i++;
                    k++;
                }
                else break;
            }
            L.a[L.top]=temp;
        }
        else  if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')        //遇到运算符进行计算
        {
            switch(s[i])
            {
            case '+':
                e=L.a[L.top-1]+L.a[L.top];
                break;
            case '-':
                e=L.a[L.top-1]-L.a[L.top];
                break;
            case '*':
                e=L.a[L.top-1]*L.a[L.top];
                break;
            case '/':
                e=L.a[L.top-1]/L.a[L.top];
                break;
            }
            L.a[L.top-1]=e;                                          //往前一位存储
            L.a[L.top]=0;
            L.top--;
        }
    }
    printf("%.0lf",L.a[L.top]);                                    //输出最后结果
    return 0;
}

原文：https://blog.csdn.net/hanmiaobei7428/article/details/82049881

中缀表达式的求值问题

表达式的求值问题（堆栈）
0. 解决目标
将形如2*(9+6/3-5)+4表达式求值的思想

  1. 后缀表达式的求值

形如在这里插入图片描述这里写图片描述的表达式如何求值？

（翻译成中缀表达式为：6/2-3+4*2，我们不进行中缀表达式的翻译操作，只是为了方便理解中间的过程）
从左向右“扫描”，逐个处理运算数和运算符号

遇到运算数怎么办？如何“记住”目前还不未参与运算的数？

遇到运算符号怎么办？对应的运算数是什么？
在这里插入图片描述
下图是一种解决办法。
在这里插入图片描述
这里使用一种结构，由于长得像先称之为“槽”，这种槽有什么特点？

1.只能存放数字
2.存放的数字只能后面进来的先出
这里有个问题，如果是符号怎么办呢？
我们提供一种解决办法，如果遇到符号，则将槽最顶部的数字与前一个数字从槽中拿出，进行操作，操作为：

1.前一个数字 运算符 槽最顶部的数字
2.并讲运算结果 再放入槽中
3.直至所有东西都按从左到右的顺序 尝试进入槽中，便得到结果。

这种能够解决后缀表达式的求值问题的结构——“槽”，就是堆栈。它是一种线性存储结构，后入先出。
我们用堆栈解决了后缀表达式的求值问题，那么问题来了，如何将中缀表达式转换成后缀表达式呢？
##2. 中缀化后缀

目标：将形如2*(6/3+4)-5的中缀表达式化成 2 6 3 / 4 + * 5 -的后缀表达式
带括号的表达式看起来比较复杂，我们先看没有括号的转换。

小目标：将形如2+9/3-5的中缀表达式化成2 9 3 / + 5 - 的后缀表达式
构造一种堆栈，只能存放符号，同样遵循后入先出的原则。
有两个问题
1.遇到数字怎么办？
2.堆栈中的符号怎么处理？
第一个问题很简单，输出即可，因为我们只需要求表达式，并不需要同时计算。
第二个问题，因为符号有优先级，当将符号放入堆栈时，比较其与前一个符号的优先级，若低于，则先输出前一个运算符。这个也很好理解，高优先级的运算先进行。
解决过程如下图所示。
在这里插入图片描述
那如果带括号要怎么解决呢？问题有：

1.括号也算一种符号，但括号不参与运算，
2.括号提供一种优先级，括号里面的运算优先级最高

第一个问题，我们在后缀表达式转换成值的时候是直接进行操作的，利用顺序已经将括号的功能包括进去，但只是不显示括号而已。具体解决是在一对括号齐全时，将其中的运算符输出。
第二个问题，我么将括号放入堆栈之前认为其优先级最高，在放入堆栈之后，将其认为优先级最低，即只进行括号里面的优先级比较（忽略括号）。
解决过程如下图。

在这里插入图片描述
总结中缀表达式转化成后缀表达式的方法如下：

在这里插入图片描述
按照 步骤2->1->0 完成目标

学习自《数据结构：陈越》之线性结构

呼，终于把最近看的，学的，总结起来了。。。
我如果有什么地方弄得不对的，看到的道友可以在下方评论说出来，或者私信我。
学习使我们快乐~

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

数据结构

C语言中缀表达式求值(综合) 的相关文章

随机推荐

  • c++ 入门基础（一）

    第一个c 程序 include

  • MySQL5.6数据库8小时内无请求自动断开连接

    问题 最近的项目中 发现Mysql数据库在8个小时内 没有请求时 会自动断开连接 这是MySQL服务器的问题 The last packet successfully received from the server was 1 836 1

  • 从零开始做一个贪吃蛇游戏（用纯html + css + js实现，主要技术栈：vue + uniCloud）

    今天给大家分享一个贪吃蛇的小游戏 用纯html css js实现 主要技术栈 vue uniCloud 希望能对还未涉及游戏开发的小伙伴有所启发 由于技术栈很浅 希望大佬勿喷 话不多说 直接开撸 效果图如下 初始化项目 本项目是基于uni

  • 网络基础——TCP与UDP的区别

    Web基础 COOKIE与SESSION的区别 如上表格 区别总结如下 1 连接性质不同 TCP是面向有连接 而UDP是面向无连接的 所谓的面向有连接 通俗讲是指传输数据时 是否需要先建立通讯 确认对方在 并且有空接收数据 面向无连接 是不

  • 探索loss.backward() 和optimizer.step()的关系并灵活运用

    loss backward 和optimizer step 的关系及灵活运用 在deep learning的模型训练中 我们经常看到如下的代码片段 loss backward optimizer step 那么 这两个函数到底是怎么联系在一

  • layui数据可视化_利用ggplot2进行数据可视化

    2020 04 25 1 1 first step 意识到ggplot绘制其实是由一层层图层组成 一个命令即可增加一层 ggplot data mpg geom point mapping aes x displ y hwy ggplot

  • TensorFlow 2.0教程05：跨多个节点的分布式培训

    分布式训练允许扩大深度学习任务 因此可以学习更大的models或以更快的速度进行训练 在之前的教程中 我们讨论了如何MirroredStrategy在单个节点 物理机器 内实现多GPU训练 在本教程中 我们将解释如何在多个节点之间进行分布式

  • 永磁同步电机矢量控制（五）——波形记录及其分析

    恰饭一下 已经过了工作的年纪 在这里稍微出一下自己做的一套永磁同步电机的教程 为了解决电机控制入门难的问题 我将自己从一知半解到现在的学习记录整理成十个部分学习教程 从基础的矢量控制 到应用性较强的MTPA 弱磁控制等 最后深入到无速度传感

  • [1024]python sqlalchemy中create_engine用法

    用法 engine create engine dialect driver username password host port database dialect 数据库类型 driver 数据库驱动选择 username 数据库用户名

  • 论文笔记-深度估计(7)-CNN-SLAM Real-time dense monocular SLAM with learned depth prediction

    CVPR2017 CNN SLAM Real time dense monocular SLAM with learned depth prediction 关键词 基于CNN的单张图深度估计 语义SLAM 半稠密的直接法SLAM 作者提出

  • Unity 3D游戏十一：坦克大战

    前言 中山大学数据科学与计算机学院3D游戏课程学习记录博客 游戏代码 gitee 参考师兄的博客 师兄博客 游戏视频 bilibili 游戏要求 从商店下载游戏 Kawaii Tank 或 其他坦克模型 构建 AI 对战坦克 具体要求如下

  • vue替换url中的#为指定字符串

    url符号 处理 替换 号为asqm function replaceUrlJINtoAAB console log 123366 测试全局方法 添加时间 2022 7 21 15 05 43 url符号 处理 替换 号为asqm cons

  • HTML 快速入门

    目录 概念 快速入门 语法 基本标签 1 文件标签 2 文本标签 3 图片标签 4 列表标签 5 链接标签 6 div和span 7 语义化标签 8 表格标签 案例 旅游网站首页 表单标签 form标签 表单项标签 1 input 2 se

  • RocketMQ（一）—— 基本使用

    目录 1 RocketMQ基本使用 1 启动 2 测试 3 关闭 2 集群简介 特点 集群模式 工作流程 3 双主双从集群搭建 关闭防火墙 环境变量配置 创建消息存储路径 broker配置文件 启动 集群监控平台搭建 4 消息发送 1 基本

  • centos7安装mysql8.0.17初始化错误

    2019 08 22T13 21 17 518044Z 0 System MY 013169 Server root soft app mysql bin mysqld mysqld 8 0 17 initializing of serve

  • 免费下载正版office（仅限笔记本用户）

    买笔记本的时候 一般都会赠送正版office 但是由于重装系统等等某些原因 office找不到 面对这种情况 不用去网上找免登录的下载方法 详情请看下面方法 一 登录微软官网 注 一定要登录你买电脑时注册微软的账户 一般是qq邮箱 网址如下

  • 如何在前端完美控制浏览器兼容性问题

    分享一些好玩的代码 看看哈 function t n e var a 0 r isVisible function t var n t getBoundingClientRect e n width n right 0 n left 0 a

  • OpenGL 4.0的Tessellation Shader（细分曲面着色器）

    OpenGL 4 0的Tessellation Shader 细分曲面着色器 细分曲面着色器 Tessellation Shader 处于顶点着色器阶段的下一个阶段 我们可以看以下链接的OpenGL渲染流水线的图 https www ope

  • import pandas as pd 报错_chapter5-1 数据处理常见bug报错整理1

    本篇文章中 笔者把之前自己码代码的过程中出现的一些已解决的常见bug和解决方法进行了整理 还在不断更新中 主要内容有 一 与读取CSV文件有关的报错 1 1 utf 8 codec can t decode 1 2 pandas read

  • C语言中缀表达式求值(综合)

    题前需要了解的 中缀 后缀表达式是什么 不知道你们知不知道 反正我当时不知道 搜的百度 基本思路 先把输入的中缀表达式 后缀表达式 进行计算得出结果 栈 先进先出 先进后出 中缀转后缀 先把转换后的后缀表达式存入字符数组 从左至右依次读取

热门标签