四则计算机实现(C++)(堆栈的应用)

news/2024/4/17 7:37:40

算法要求:

  1. 输入一个数学表达式(假定表达式输入格式合法),计算表达式结果并输出。
  2. 数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、) ”构成,例如 2 + 3 * ( 4 + 5 ) - 6 / 4。
  3. 变量、输出采用整数,只舍不入。

图解算法思想:

1、图中1、2、3、4~~表示操作的前后顺序

2、图中橙色栈用来处理数字,黄色用来处理运算符。

3、本图实际上将中缀转后缀、后缀求值两步整合在一起  

最后一步执行:取出‘-’,然后43-6=37,作为最后结果。

 

程序思想流程图:

 

代码如下:

【实验全部代码】
#include <iostream>
#include <string>
using namespace std;// 写一个栈的模板函数,因为下面需要用到 int 和 char 两种 stack 类型,且方法一样
template <class T>
class Stack {
private:T data[1001];int size; // 同时承担 top 的作用public:Stack() {size = 0;}~Stack() {size = 0;}T pop() {//出栈size--;return data[size];}void push(T a) {//入栈data[size++] = a;}T front() {//返回栈顶元素return data[size - 1];}void clear() {//清除栈中元素,非物理清除,仅逻辑清除size = 0;}bool empty() {//判空return (size == 0);}
};// 中序转后序函数
string inToSuffix(string s) {string result = "";int size = s.size();Stack<char> a;for (int i = 0; i < size; i++) {
//对括号的处理if (s[i] == '(') {a.push(s[i]);} else if (s[i] == ')') {if (!a.empty()) {char t = a.pop();while (t != '(' && !a.empty()) {result.push_back(t);t = a.pop();}}
//加减乘除的处理} else if (s[i] == '+' || s[i] == '-') { // 加减的等级是最低的while (!a.empty()) {if (a.front() == '(') {break;} else { // 加减和乘除的处理方式一样,都是弹出result.push_back(a.pop());}}a.push(s[i]);} else if (s[i] == '*' || s[i] == '/') {while (!a.empty()) {if (a.front() == '(') {break;} else if (a.front() == '*' || a.front() == '/') { // 仅仅乘除被弹出,加减留在里面result.push_back(a.pop());} elsebreak; // 如果遇到加减,则要直接 break,否则死循环}a.push(s[i]);
//数字的处理} else if (s[i] >= '0' && s[i] <= '9') {result.push_back(s[i]);} else {cout << "存在非法输入" << endl;break;}}while (!a.empty()) { // 最后要把栈中所有东西一一输出result.push_back(a.pop());}return result;
}int suffix_print(string s) { // 后缀表达式核心就在于运算顺序,所以中缀中的括号在后缀中已经转化为数字和运算的前后顺序Stack<int> a;int size = s.size();for (int i = 0; i < size; i++) {if (s[i] >= '0' && s[i] <= '9')a.push(s[i] - '0');else {int s2 = a.pop();int s1 = a.pop();if (s[i] == '*') {a.push(s1 * s2);} else if (s[i] == '+') {a.push(s1 + s2);} else if (s[i] == '/') {a.push(s1 / s2);} else {a.push(s1 - s2);}}}return a.front();
}int main() {cout << "Input" << endl;string input;cin >> input;cout << "Output" << endl;string inpute1 = inToSuffix(input);cout << "=" << suffix_print(inpute1) << endl;cout << "End";return 0;
}

感悟与算法分析: 

本题是实现计算器的制作。可以分为三个子问题:括号作用在数据结构中的实现、如何将中缀表达式化为后缀表达式、如何将后缀表达式的值计算出来

针对

问题一:对于一个表达式,我们采用栈的方式去存储。那么如何用栈来处理括号问题呢?

  1. 遇到括号则判断是否是哪一类型括号
  2. 如果是左括号则直接压入栈,后续将括号内的符号一一压入,期间这些符号也可以弹出,但是左括号一直不弹出。直到遇到右括号,则左括号上面以及左括号本身都要一并弹出。但是左括号并不输出、同时右括号并不压入栈。
  3. 如果右括号遇到但是栈中所有元素都弹出也没有左括号则报错误。若是左括号到程序最后也没有弹出则报错误

问题二:如何将中缀表达式转化为后缀表达式只要遵循下面这几个要求即可。

  1. 利用栈结构来处理
  2. 遇到1~9的数字直接printf打印输出,栈仅仅记录运算符号。
  3. 遇到括号则分为左右两种括号按照问题一的要求来处理
  4. 遇到+-*/运算符则要先把栈中优先级等于或小于该运算符的一一弹出,然后把该运算符本身压入栈中。

所以本问题可以利用多次的if判断语句,将问题分为这几种情况分别按照要求去处理

问题三:后缀表达式的求值也同样分为以下几个步骤来处理即可。

  1. 同样需要栈,但是栈此时存放的是数字
  2. 遇到数字则直接压入栈
  3. 遇到一个运算符则取出栈顶的两个元素,按照先输出的在左边、后输出的在右边与该运算符进行计算,并将运算结果重新压回栈中
  4. 在后缀表达式结束后,将栈中的元素取出来即为最后的答案

综上来说本题考察的主要是波兰表达式和逆波兰表达式的转化,以及逆波兰表达式的计算。而这些计算借助的数据结构就是栈。程序在书写的过程中最需要注意的就是if、elseif的分类处理。有一些类处理中需要用break来退出,否则会让程序进入死循环。其他一些注意点都在程序注释中标明。

仅供参考,一定不要直接复制!!!查重很严的!!! 


https://www.xjx100.cn/news/3119072.html

相关文章

SQL Server对象类型(8)——4.8.约束(Constraint)

4.8. 约束(Constraint) 4.8.1. 约束概念 与Oracle中的一样,SQL Server中,约束是虚的、被定义的数据库对象,其本身并不存储数据,其通过一些内置或用户自定义逻辑来实现对表中数据的检查和限制,以使这些表数据符合某个或某些规则或标准,从而实现数据的规则化、标准化和…

linux socket套接字

文章目录 socket流socket&#xff08;TCP&#xff09;数据报socket&#xff08;UDP&#xff09; 讨论 socket 所谓套接字&#xff0c;就是对网络中不同主机上的应用程序之间进行双向通信的端点的抽象。一个套接字就是网络上进程通信的一端&#xff0c;套接字提供了应用层进程利…

Hive_last_value()

在SQL中&#xff0c;LAST_VALUE()函数是一个窗口函数&#xff0c;用于返回窗口内的最后一个值。窗口函数允许你在一组行上执行计算&#xff0c;这组行与当前行有某种关系。可以将它们想象为与当前行相关的“窗口”。 LAST_VALUE()函数通常与OVER()子句一起使用&#xff0c;后者…

Node.js 万字教程

0. 基础概念 Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境&#xff0c;使用了一个事件驱动、非阻塞式 I/O 模型&#xff0c;让 JavaScript 运行在服务端的开发平台。 官方地址&#xff1a;https://nodejs.org/en 中文地址&#xff1a;https://nodejs.org/zh-cn 代…

基于Django+Tensorflow卷积神经网络鸟类识别系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介系统概述系统功能核心技术系统架构系统优势 二、功能三、系统四. 总结  总结 一项目简介 介绍一个基于DjangoTensorflow卷积神经网络鸟类识别系统是一个非…

掌握Flask:从入门到精通指南

掌握Flask&#xff1a;从入门到精通指南 Flask 是一个轻量级的 Python Web 应用程序框架&#xff0c;具有简单易学、灵活性高等特点&#xff0c;适合用于快速开发 Web 应用程序。本文将全面介绍 Flask 框架的各个方面&#xff0c;包括基本概念、路由、模板渲染、表单处理、数据…

Golang rsa 验证

一下代码用于rsa 签名的验签&#xff0c; 签名可以用其他语言产生。也可以用golang生成。 package mainimport ("crypto""crypto/rsa""crypto/sha256""crypto/x509""encoding/pem""errors""fmt" )fun…

开源播放器GSYVideoPlayer + ViewPager2 源码解析

开源播放器GSYVideoPlayer ViewPager2 源码解析 前言一、GSYVideoPlayer&#x1f525;&#x1f525;&#x1f525;是什么&#xff1f;二、源码解析1.ViewPager2Activity 总结 前言 本文介绍GSYVideoPlayer源码中关于ViewPager2 GSYVideoPlayer 实现的滑动播放列表的实现原理。…