Typical use cases for knapsacks, queues, and stacks

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 .