中缀表达式转后缀表达式与后缀表达式计算（详解）

**中缀表达式转后缀表达式的一般步骤如下：
1：创建一个空的栈和一个空的输出列表。
2：从左到右扫描中缀表达式的每个字符。
3：如果当前字符是操作数，则直接将其加入到输出列表中。
4：如果当前字符是运算符，比较其与栈顶运算符的优先级：

  1. a. 如果栈为空或栈顶运算符是左括号"(“，则直接将当前运算符入栈。
    b. 如果当前运算符的优先级高于栈顶运算符的优先级，则将当前运算符入栈。
    c. 如果当前运算符的优先级低于或等于栈顶运算符的优先级，则将栈顶运算符弹出并加入到输出 列表中，
    直到栈为空或栈顶运算符的优先级低于当前运算符的优先级，然后将当前运算符入栈。
    d. 如果当前字符是右括号”)“，则依次弹出栈中的运算符并加入到输出列表中，
    直到遇到左括号”("为止，此时将左括号出栈且不加入输出列表。

    5：扫描完整个中缀表达式后，将栈中剩余的运算符依次弹出并加入到输出列表中。
    6：输出列表即为转换后的后缀表达式。
    举个例子：
    中缀表达式：2 + 3 * (4 - 1)
    转换为后缀表达式：2 3 4 1 - * +
    具体实现需要根据编程语言和数据结构来进行操作。    **
    在这里插入图片描述

项目结构
在这里插入图片描述项目头文件结构QueueStorage.h
在这里插入图片描述项目头文件代码

#ifndef LINKSTACK_H
#define LINKSTACK_H
#include <stdio.h>
#include <stdlib.h>
// 链式栈的节点
typedef struct LINKNODE {
	struct LINKNODE* next;
}LinkNode;
// 链式栈
typedef struct LINKSTACK {
	LinkNode head;
	int size;

}LinkStack;


// 初始化函数
LinkStack* Init_LinkStack();
// 入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data);
// 出栈
void Pop_LinkStack(LinkStack* stack);
// 返回栈顶元素
LinkNode* TopLinkStack(LinkStack* stack);
// 返回栈元素的个数
int Size_LinkStack(LinkStack* stack);
// 清空栈
void Clear_LinkStack(LinkStack* stack);
// 销毁栈
void FreeSpace_LinkStack(LinkStack* stack);
#endif

项目cpp文件QueueStorage.cpp
在这里插入图片描述项目cpp文件代码QueueStorage.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include "QueueStorage.h"

// 初始化函数
LinkStack* Init_LinkStack() {
    LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
    stack->head.next = NULL;
    stack->size = 0;
    return stack;
};
// 入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data) {
    if (stack == NULL) {
        return;
    }
    if (data == NULL) {
        return;
    }
    // 入栈
    data->next = stack->head.next;
    stack->head.next = data;
    stack->size++;
};
// 出栈
void Pop_LinkStack(LinkStack* stack) {
    if (stack == NULL) {
        return;
    }
    if (stack->size == 0) {
        return;
    }

    // 第一个有效节点
    LinkNode* pNext = stack->head.next;
    stack->head.next = pNext->next;
    stack->size--;



};
// 返回栈顶元素
LinkNode* TopLinkStack(LinkStack* stack) {
    if (stack == NULL) {
        return NULL;
    }
    if (stack->size == 0) {
        return NULL;
    }
    // 返回栈顶元素
    return stack->head.next;
};

// 返回栈元素的个数
int Size_LinkStack(LinkStack* stack) {
    if (stack == NULL) {
        return -1;
    }
    return stack->size;
};
// 清空栈
void Clear_LinkStack(LinkStack* stack) {
    if (stack == NULL) {
        return;
    }
    // 清空栈
    stack->head.next = NULL;
    stack->size = 0;

};
// 销毁栈
void FreeSpace_LinkStack(LinkStack* stack) {
    if (stack == NULL) {
        return;
    }
    free(stack);
};

项目主文件截图
在这里插入图片描述项目主文件代码main.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include "QueueStorage.h"


int IsNumber(char c) {
	return c >= '0' && c <= '9';
}
// 判断是不是左括号
int IsLeft(char c) {
	return c == '(';
}
// 判断是不是右括号
int IsRight(char c) {
	return c == ')';
}
// 判断是不是运算符号
int IsOperator(char c) {
	return c == '+' || c == '-' || c == '*' || c == '/';
}
//返回运算符号的优先级
int GetPriority(char c) {
	if (c == '*' || c == '/') {
		return 2;
	}
	if (c == '+' || c == '-') {
		return 1;
	}
	return 0;
}




//使用企业链表的方式进行实现需要添加结构体
typedef struct MYCHAR {
	LinkNode node;
	char* p;

}MyChar;


// 对于数字的操作
void NumberOperate(char* p) {
	printf("%c", *p);
}
// 创建MyChar
MyChar* CreateMyChar(char* p) {
	MyChar* mychar = (MyChar*)malloc(sizeof(MyChar));
	mychar->p = p;
	return mychar;
}

// 对于左括号的操作
void LeftOperate(LinkStack* stack,char* p) {
	Push_LinkStack(stack, (LinkNode*)CreateMyChar(p));
}
// 对于右括号的操作
void RightOperate(LinkStack* stack) {
	// 判断栈中是否存在元素
	while (Size_LinkStack(stack) > 0) {
		// 将里面的元素取出
		MyChar* mychar = (MyChar*)TopLinkStack(stack);
		// 如果匹配到左括号的话就弹出
		if (IsLeft(*(mychar->p))) {
			Pop_LinkStack(stack);
			break;
		}
		// 输出
		printf("%c", *(mychar->p));
		// 弹出
		Pop_LinkStack(stack);
		// 释放内存
		free(mychar);
	}
}
// 运算符号的操作
void OperatorOperate(LinkStack* stack, char* p) {
		

		// 取出栈顶符号
		MyChar* mychar = (MyChar*)TopLinkStack(stack);
		if (mychar == NULL) {
			Push_LinkStack(stack, (LinkNode*)CreateMyChar(p));
			return;
		}
		// 如果栈顶优先级低于符号的优先级直接入栈
		if (GetPriority(*(mychar->p) < GetPriority(*p))) {
			Push_LinkStack(stack,(LinkNode*)CreateMyChar(p));
			return;
		}
		else {
			// 如果栈顶符号优先级不低
			while (Size_LinkStack(stack) > 0) {

				 MyChar* mychar2 = (MyChar*)TopLinkStack(stack);

				// 如果优先级低当前的符号入栈
				if (GetPriority(*(mychar2->p)) < GetPriority(*p)) {
					Push_LinkStack(stack, (LinkNode*)CreateMyChar(p));
					break;
				}
				// 输出
				printf("%c ", *(mychar2->p));
				// 弹出
				Pop_LinkStack(stack);
				// 释放
				free(mychar2);
			}
		}
}

int main()
{
	/*
	    栈的应用：中缀表达式转后缀表达式

	*/
	char* str = (char *)"8 + (3 - 1) * 5";
	// 遍历字符串
	char* p = str;
	// 创建栈
	LinkStack* stack = Init_LinkStack();

	while (*p != '\0') {
	     // 判断是否数数字，如果是数字的话直接输出
		if (IsNumber(*p)) {
			NumberOperate(p);
		}
		// 判断是不是左括号，如果是左括号直接进栈
		if (IsLeft(*p)) {
			LeftOperate(stack,p);
		}
		// 如果是右括号的话将栈顶符号弹出知道匹配到左括号为止
		if (IsRight(*p)) {
			RightOperate(stack);
		}

		// 如果是运算符号的话
		if (IsOperator(*p)) {
			OperatorOperate(stack,p);
		}
		p++;
		
	}
	//将栈中剩余的元素弹出并输出
	while (Size_LinkStack(stack) > 0) {
		MyChar* mychar = (MyChar*)TopLinkStack(stack);
		printf("%c", *(mychar->p));
		Pop_LinkStack(stack);
		free(mychar);
	}

	system("pause");
	return 0;
}

修改运行界面
在这里插入图片描述在这里插入图片描述在这里插入图片描述项目运行结果

在这里插入图片描述
后缀表达式相关原理

在这里插入图片描述计算这个后缀表达式"2 3 4 1 - * +"。**

首先，我们从左到右扫描后缀表达式，遇到数字就将其入栈，遇到运算符则将栈顶的两个数字弹出进行计算，然后将结果入栈。
具体计算过程如下：

  1. 将2和3入栈
  2. 遇到4，入栈
  3. 遇到1，入栈
  4. 遇到减号"-"，弹出栈顶两个数字1和4，计算4-1=3，将结果3入栈
  5. 遇到乘号""，弹出栈顶两个数字3和3，计算33=9，将结果9入栈
  6. 遇到加号"+"，弹出栈顶两个数字9和2，计算9+2=11，将结果11入栈
  7. 后缀表达式扫描结束，栈顶的数字11即为最终的计算结果。

主文件
在这里插入图片描述
主文件截图
在这里插入图片描述主文件代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include "QueueStorage.h"

int IsNumber2(char c) {
    return c >= '0' && c <= '9';
}
typedef struct MYNUM{
    LinkNode node;
    int val;

}MyNum;
int Calculate(int left,int right,char c) {
    int ret = 0;
    switch (c) {
       case '+':
            ret = left + right;
            break;
       case '-':
           ret = left - right;
           break;
       case '*':
           ret = left * right;
           break;
       case '/':
           ret = left / right;
           break;
         default:
            break;
    }
    return ret;
}


int main(void) {
    /*
       根据后缀表达式求解

    */
    char* str = (char *)"831-5*+";
    char* p = str;
    // 创建栈
    LinkStack* stack = Init_LinkStack();
    // 对后缀表达式进行扫描
    while (*p != '\0') {
        // 如果是数字直接入栈
        if (IsNumber2(*p)) {
            MyNum* num = (MyNum*)malloc(sizeof(MyNum));
            num->val = *p - '0';
            Push_LinkStack(stack,(LinkNode*)num);
        }
        else {
            MyNum* right = (MyNum*)TopLinkStack(stack);
            // 如果是运算符的话，先从栈中弹出右操作数
            int rightNum = right->val;
            Pop_LinkStack(stack);
            free(right);
            // 取出左操作数
            MyNum* left = (MyNum*)TopLinkStack(stack);
            int leftNum = left->val;
            Pop_LinkStack(stack);
            free(left);
            int ret = Calculate(leftNum, rightNum, *p);
            // 结果入栈
            MyNum* num = (MyNum*)malloc(sizeof(MyNum));
            num->val = ret;
            Push_LinkStack(stack, (LinkNode*)num);
        }
        p++;
    }
    if (Size_LinkStack(stack) == 1) {
        MyNum* num = (MyNum*)TopLinkStack(stack);
        printf("运算结果是%d\n", num->val);
        Pop_LinkStack(stack);
        free(num);
    }
    // 释放栈
    FreeSpace_LinkStack(stack);
    system("pause");
    return 0;
}

运行结果展示：
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/228598.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

你是外包，麻烦不要偷吃零食，注意素质..

你是外包，麻烦不要偷吃零食，注意素质..

我自己没经历过外包&#xff0c;靠自己的所见所闻可能写出来的东西会很主观&#xff0c;所幸我有不少外包的读者&#xff0c;还有几个在外包工作或工作过的朋友&#xff0c;在跟她们深度交流之后&#xff0c;这这里聊一下我自己的一些看法。 注&#xff1a;本文不代表所有外包公…
阅读更多...
Python接口自动化测试数据和代码分离解析

Python接口自动化测试数据和代码分离解析

common中存放的是整个项目中公共使用的封装方法 从工程目录上可以看到区分 datas中专门存放测试数据(yml文件) cases中专门集中存放测试用例 ... 数据分离的第一步先找到工程项目路径 1 2 3 4 5 6 7 8 9 10 11 12 # -*- encoding: utf-8 -*- """ __Software…
阅读更多...
智能运维相关算法总结

智能运维相关算法总结

概念&#xff1a; 智能运维&#xff08;AIOps&#xff09;是基于已有的运维数据&#xff08;日志、监控信息 、应用信息&#xff09;并通过机器学习的方法来进一步解决自动化运维没办法解决的问题&#xff0c;其核心是机器学习和大数据平台。 目标&#xff1a; 事前预警&…
阅读更多...
C++ day59 下一个更大元素Ⅱ 接雨水

C++ day59 下一个更大元素Ⅱ 接雨水

题目1&#xff1a;503 下一个更大元素Ⅰ 题目链接&#xff1a;下一个更大元素Ⅱ 对题目的理解 返回循环数组中每个元素的下一个更大元素&#xff0c; 数字x的下一个更大元素是循环等的搜索它的最近的下一个更大的数 数组的中至少有一个元素 本题难点在于循环遍历这里&…
阅读更多...
新手搭建知识付费平台必备攻略：如何以低成本实现高转化？

新手搭建知识付费平台必备攻略：如何以低成本实现高转化？

我有才知识付费平台 一、引言 随着知识经济的崛起&#xff0c;越来越多的知识提供者希望搭建自己的知识付费平台。然而&#xff0c;对于新手来说&#xff0c;如何以低成本、高效率地实现这一目标&#xff0c;同时满足自身需求并提高客户转化率&#xff0c;是一大挑战。本文将…
阅读更多...
【面试经典150 | 二叉树】从前序与中序遍历序列构造二叉树

【面试经典150 | 二叉树】从前序与中序遍历序列构造二叉树

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;递归 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到的数据结构等内容…
阅读更多...
Java数字化健康卫生智慧云HIS系统源码

Java数字化健康卫生智慧云HIS系统源码

基于云计算技术的B/S架构云HIS集挂号、处方、收费、取药、病历于一体,完全适配各类中小型医院、诊所。 一、云 HIS定义 1、云 HIS 系统是运用云计算、大数据、物联网等新兴信息技术&#xff0c;按照现代医疗卫生管理要求&#xff0c;在一定区域范围内以数字化形式提供医疗卫生…
阅读更多...
软文营销全过程分享，助力企业提高宣传效率

软文营销全过程分享，助力企业提高宣传效率

数字化时代下&#xff0c;软文营销已经成为许多企业推广品牌的手段&#xff0c;但是在营销过程中大部分企业认为只需要写好文章进行发布就够了&#xff0c;这其实是错误的&#xff0c;只会浪费企业的时间精力。今天媒介盒子就分享软文营销全过程&#xff0c;助力企业提高宣传效…
阅读更多...
cpu 300% 爆满 内存占用不高 排查

cpu 300% 爆满 内存占用不高 排查

top查询 cpu最高的PID ps -ef | grep PID 查看具体哪一个jar服务 jstack -l PID > ./jstack.log 下载/打印进程的线程栈信息 可以加信息简单分析 或进一步 查看堆内存使用情况 jmap -heap Java进程id jstack.log 信息示例 Full thread dump Java HotSpot(TM) 64-Bit Se…
阅读更多...
SpringMVC 案例

SpringMVC 案例

文章目录 前言1. 计算器1.1 准备前端代码1.2 测试前端代码1.3 完成后端代码1.4 验证程序 2. 留言板2.1 前端代码准备2.2 测试前端代码2.3 完成前后端交互代码2.4 完成后端代码2.5 案例测试2.6 完善前后端交互2.7 完善后端代码2.8 完整功能测试 lombok简单的方式添加Lombok工具3…
阅读更多...
小视频怎么做成二维码？视频二维码3步生成

小视频怎么做成二维码？视频二维码3步生成

在日常工作和生活中经常会看到各种类型的小视频、短视频&#xff0c;比如网页、抖音等等的视频都是可以下载查看的。当我们想要将下载视频分享给多个人看时&#xff0c;生成二维码的方式会更加的方便&#xff0c;那么视频如何生成二维码呢&#xff1f;下面就将快捷生成二维码的…
阅读更多...
spring boot 3.2 整合 keycloak

spring boot 3.2 整合 keycloak

背景 项目中用到 keycloak&#xff0c;因此其他所有管理页面要集成 keycloak 做统一登录认证。 Keycloak 侧配置 容器方式启动 keycloak 服务端 docker run -d --name mykeycloak -p 8080:8080 -e KEYCLOAK_ADMINadmin -e KEYCLOAK_ADMIN_PASSWORDadmin ke…
阅读更多...
LeetCode 每日一题 Day 6（DFS+BFS)

LeetCode 每日一题 Day 6（DFS+BFS)

1466. 重新规划路线 n 座城市&#xff0c;从 0 到 n-1 编号&#xff0c;其间共有 n-1 条路线。因此&#xff0c;要想在两座不同城市之间旅行只有唯一一条路线可供选择&#xff08;路线网形成一颗树&#xff09;。去年&#xff0c;交通运输部决定重新规划路线&#xff0c;以改变…
阅读更多...
【GEE笔记】在线分类流程，标注样本点、分类和精度评价

【GEE笔记】在线分类流程，标注样本点、分类和精度评价

GEE在线分类流程 介绍 GEE&#xff08;Google Earth Engine&#xff09;是一个强大的地理信息处理平台&#xff0c;可以实现在线的遥感影像分析和处理。本文将介绍如何使用GEE进行在线的分类流程&#xff0c;包括标注样本点、分类和精度评价。本文以2020年5月至8月的哨兵2影像…
阅读更多...
优秀案例 | 元宇宙双语财经科技主播“舒望”主持首届粤港澳大湾区元宇宙国际传播论坛

优秀案例 | 元宇宙双语财经科技主播“舒望”主持首届粤港澳大湾区元宇宙国际传播论坛

12月6日&#xff0c;由南方财经全媒体集团指导、大湾区元宇宙国际传播实验室(GBA MIC Lab&#xff09;主办、南财国际传播中心和21世纪经济报道共同承办&#xff0c;以“多元共创开放共享”为主题的首届粤港澳大湾区元宇宙国际传播论坛在广州隆重开幕。 “立足湾区&#xff0c;…
阅读更多...
解决bash: conda: command not found

解决bash: conda: command not found

阅读更多...
【GEE笔记】随机森林特征重要性计算并排序

【GEE笔记】随机森林特征重要性计算并排序

随机森林是一种基于多个决策树的集成学习方法&#xff0c;可以用于分类和回归问题。在gee中可以使用ee.Classifier.smileRandomForest()函数来创建一个随机森林分类器&#xff0c;并用它来对影像进行分类。 随机森林分类器有一个重要的属性&#xff0c;就是可以计算每个特征&a…
阅读更多...
【沁恒蓝牙MESH】CH582串口中断内存溢出导致MCU频繁重启

【沁恒蓝牙MESH】CH582串口中断内存溢出导致MCU频繁重启

本文主要记录了【沁恒蓝牙mesh】CH582串口中断内存溢出导致MCU频繁重启 由于开发疏忽&#xff0c;导致的数组内存溢出&#xff0c;是入门嵌入式开发经常忽视的错误&#xff0c;用以记录&#xff0c;共勉&#xff01;&#xff01; 目录 1. 遇到问题描述以及解决1.1 问题一&#…
阅读更多...
案例063:基于微信小程序的传染病防控宣传系统

案例063:基于微信小程序的传染病防控宣传系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder …
阅读更多...
都2023年了还在搜索Maven是什么?赶紧来学习(超详细一文搞懂)

都2023年了还在搜索Maven是什么?赶紧来学习(超详细一文搞懂)

文章目录 前言1. 到底什么是 Maven2. 为什么要学Maven3. 创建一个 Maven 项目4. Maven 核心功能4.1 项目构建4.2 依赖管理 4. Maven 仓库4.1 本地仓库4.2 中央仓库4.3 私有服务器, 也称为私服 5. Maven 设置国内源5.1 配置当前项目setting5.2 设置新项目的setting 总结 前言 我…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站