当前位置:网站首页>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 .
边栏推荐
- Zheng Qing 21 ACM is fun. (3) part of the problem solution and summary
- [jailhouse article] jailhouse hypervisor
- 记录QT内存泄漏的一种问题和解决方案
- Haut OJ 1245: large factorial of CDs --- high precision factorial
- [jailhouse article] performance measurements for hypervisors on embedded ARM processors
- Annotation and reflection
- 过拟合与正则化
- [to be continued] [UE4 notes] L2 interface introduction
- object serialization
- 【Jailhouse 文章】Look Mum, no VM Exits
猜你喜欢
Acwing 4300. Two operations
游戏商城毕业设计
object serialization
Remote upgrade afraid of cutting beard? Explain FOTA safety upgrade in detail
Sword finger offer 53 - ii Missing numbers from 0 to n-1
【Jailhouse 文章】Jailhouse Hypervisor
剑指 Offer 58 - II. 左旋转字符串
Binary search basis
[jailhouse article] performance measurements for hypervisors on embedded ARM processors
On-off and on-off of quality system construction
随机推荐
lxml.etree.XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
CCPC Weihai 2021m eight hundred and ten thousand nine hundred and seventy-five
R语言【数据集的导入导出】
Find a good teaching video for Solon framework test (Solon, lightweight application development framework)
Sword finger offer 09 Implementing queues with two stacks
使用Electron开发桌面应用
Zzulioj 1673: b: clever characters???
Add level control and logger level control of Solon logging plug-in
Personal developed penetration testing tool Satania v1.2 update
剑指 Offer 05. 替换空格
个人开发的渗透测试工具Satania v1.2更新
A new micro ORM open source framework
【Jailhouse 文章】Performance measurements for hypervisors on embedded ARM processors
Pointnet++的改进
剑指 Offer 58 - II. 左旋转字符串
Haut OJ 1245: large factorial of CDs --- high precision factorial
Sword finger offer 04 Search in two-dimensional array
Common optimization methods
Double pointer Foundation
Hang wait lock vs spin lock (where both are used)