当前位置:网站首页>Typical use cases for knapsacks, queues, and stacks
Typical use cases for knapsacks, queues, and stacks
2022-07-05 05:35:00 【Raise items】
List of articles
knapsack
The following example is to calculate all double
It's worth it The average and Sample standard deviation .
#include <iostream>
#include <cmath>
#include "bag.h"
int main()
{
Bag<double> bag;
double d;
while (std::cin >> d) {
bag.Add(d);
}
double sum = 0;
for (auto x : bag) {
sum += x;
}
double mean = sum / bag.Size();
sum = 0;
for (auto x : bag) {
sum += (x - mean) * (x - mean);
}
double std = sqrt(sum / (bag.Size() - 1));
std::cout << mean << std::endl;
std::cout << std << std::endl;
return 0;
}
In order to be able to use Range for Statement traversal bag
The elements in the object , You need to add begin()
and end()
Method (deque
The iterator supports ++
operation ).
template <typename Item>
class Bag {
public:
typename std::deque<Item>::iterator begin();
typename std::deque<Item>::iterator end();
// ...
};
template <typename Item>
typename std::deque<Item>::iterator Bag<Item>::begin()
{
return dq_.begin();
}
template <typename Item>
typename std::deque<Item>::iterator Bag<Item>::end()
{
return dq_.end();
}
Running results ( Command line ctrl + D
yes EOF
):
queue
The following example is to input the standard int
Value press The order Store in an array , We don't know in advance how much memory to allocate for the array .
#include <iostream>
#include <cmath>
#include "queue.h"
int main()
{
Queue<int> qi;
int ele;
while (std::cin >> ele) {
qi.EnQueue(ele);
}
int N = qi.Size();
int arr[N];
for (int i = 0; i < N; ++i) {
arr[i] = qi.Dequeue();
}
for (int i = 0; i < N; ++i) {
std::cout << arr[i] << std::endl;
}
return 0;
}
Running results (D
Is command line input EOF
The emergence of ):
Stack
In the following example , Press the integer in the standard input The reverse Print out .
#include <iostream>
#include "stack.h"
int main()
{
Stack<int> si;
int ele;
while (std::cin >> ele) {
si.Push(ele);
}
while (!si.IsEmpty()) {
std::cout << si.Pop() << std::endl;
}
return 0;
}
Running results :
Arithmetic expression evaluation
A classic use case of stack is computation Arithmetic expressions : Enter a string , Output a value .
For the sake of simplicity , expression Do not omit parentheses ( Use parentheses instead of priority rules to do four operations ), Brackets 、 Operands 、 Between operators Space separate .
Input :( 1 + ( 2 + 3 ) * ( 4 * 5 ) )
Output :101
E.W.Dijkstra
stay 20
century 60
In the s, a very simple algorithm was invented , The process is as follows :(1)
Prepare two stacks : The stack of operands and Operator stack .(2)
Traversal arithmetic expression .(3)
take The operand is pushed into the operand stack 、 Operator push into operator stack , Ignore left parenthesis .(4)
encounter Right bracket when , eject An operator , Again eject Required operands , perform operation , Result Push the The stack of operands .(5)
When the last closing bracket is processed , There is only one operand on the stack , That is the expression result .
Code implementation :
#include <iostream>
#include <string>
#include <stdlib.h>
#include <cmath>
#include "stack.h"
using std::string;
void Calculate(Stack<string> &ops, Stack<double> &vals)
{
string op = ops.Pop();
double a = vals.Pop();
if (op == string("+")) {
double b = vals.Pop();
vals.Push(a + b);
} else if (op == string("-")) {
double b = vals.Pop();
vals.Push(b - a);
} else if (op == string("*")) {
double b = vals.Pop();
vals.Push(a * b);
} else if (op == string("/")) {
double b = vals.Pop();
vals.Push(b / a);
} else if (op == string("sqrt")) {
vals.Push(sqrt(a));
} else {
std::cout << "unknown operator" << std::endl;
}
}
int main()
{
Stack<string> ops; // Operator stack
Stack<double> vals; // The stack of operands
string str;
while (std::cin >> str) {
if (str == string("(")) {
continue;
} else if ((str == string("+")) || (str == string("-")) ||
(str == string("*")) || (str == string("/")) ||
(str == string("sqrt"))) {
ops.Push(str);
continue;
} else if (str == string(")")) {
Calculate(ops, vals);
} else {
vals.Push(atof(str.c_str()));
}
}
std::cout << vals.Pop() << std::endl;
return 0;
}
Running results :
This implementation does not provide Parameter check Mechanism .
边栏推荐
- 剑指 Offer 35.复杂链表的复制
- Daily question - longest substring without repeated characters
- 【ES实战】ES上的native realm安全方式使用
- ALU逻辑运算单元
- 使用Electron开发桌面应用
- 剑指 Offer 05. 替换空格
- Haut OJ 1221: a tired day
- YOLOv5-Shufflenetv2
- Animation scoring data analysis and visualization and it industry recruitment data analysis and visualization
- Drawing dynamic 3D circle with pure C language
猜你喜欢
SAP-修改系统表数据的方法
Binary search basis
全排列的代码 (递归写法)
Sword finger offer 09 Implementing queues with two stacks
利用HashMap实现简单缓存
[jailhouse article] look mum, no VM exits
剑指 Offer 58 - II. 左旋转字符串
Graduation project of game mall
Analysis of backdoor vulnerability in remote code execution penetration test / / phpstudy of national game title of national secondary vocational network security B module
Codeforces round 712 (Div. 2) d. 3-coloring (construction)
随机推荐
Corridor and bridge distribution (csp-s-2021-t1) popular problem solution
Yolov5 ajouter un mécanisme d'attention
PC寄存器
[jailhouse article] jailhouse hypervisor
剑指 Offer 53 - I. 在排序数组中查找数字 I
【ES实战】ES上的native realm安全方式使用
Haut OJ 1241: League activities of class XXX
kubeadm系列-02-kubelet的配置和启动
AtCoder Grand Contest 013 E - Placing Squares
Sword finger offer 53 - ii Missing numbers from 0 to n-1
YOLOv5-Shufflenetv2
Control Unit 控制部件
动漫评分数据分析与可视化 与 IT行业招聘数据分析与可视化
全国中职网络安全B模块之国赛题远程代码执行渗透测试 //PHPstudy的后门漏洞分析
Haut OJ 1347: addition of choice -- high progress addition
全排列的代码 (递归写法)
Using HashMap to realize simple cache
YOLOv5添加注意力機制
Mysql database (I)
Light a light with stm32