Perl Weekly Challenge 95, Part 2

Write a script to demonstrate Stack operations like below:

  • push($n) – add $n to the stack
  • pop() – remove the top element
  • top() – get the top element
  • min() – return the minimum element

This challenge starts off normal; push, pop, and top are regular stack operation, but it takes an unexpected twist at the end. min is not a regular stack operation. In fact, it’s not a stack operation at all. If you need a datastructure where you need to find the minimum value, a stack is a horrible choice. You ought to be using a heap, or a balanced tree instead.

Solutions

For all solutions, we let top and min print an error message if the are called on an empty stack. pop on an empty stack is a no-op.

Our input consists of a set of commands, one command per line. pop, top and min won’t take arguments, while push will be followed by a space, and the number to be pushed. There won’t be parenthesis in the input.

Perl

Perl has push and pop operations, which act on arrays, where the last element of the array acts as the top of the stack. For the min operation, we will use the min function from List::Util module:

use List::Util 'min';
my $ERROR = "Stack is empty";

my @stack;
while (<>) {
    if (/^push\s+(.*)/) {push @stack => $1}
    if (/^pop/)         {pop  @stack}
    if (/^top/)         {say  $stack [-1]  // $ERROR}
    if (/^min/)         {say  min (@stack) // $ERROR}
}

Find the complete program on GitHub.

Node.js

Node.js has push and pop methods, which, just like in Perl, act on arrays. The last element of the array acts as the top of the stack. For the min operator, we make use of Math . min.

We iterate over the input, and process each line as follows (at this point, command contains the line of input, stripped from its newline):

let stack = [];
let ERROR = "Stack is empty";
{
    let [m, operator, value] = 
         command . match (/^(push|pop|top|min)\s*(.*)$/);

    if (operator == "push") {stack . push (+value)}
    if (operator == "pop")  {stack . pop ()}
    if (operator == "top")  {
        console . log (stack . length ? stack [stack . length - 1] : ERROR)
    }
    if (operator == "min")  {
        console . log (stack . length ? Math . min (... stack)     : ERROR)
    }
}

Note the use of the unary + operator, in +value. Since we have parsed value out of the string, value is a string. If we take the minimum of a set of strings, we get the first string in alphabetic order — which is not what we want. Unary plus returns a numerical value, so we’re pushing numbers on the stack, and get the smallest number when using min.

Node.js does not flatten arrays when passed into functions, but Math . min takes a list, not an array. Therefore, we use the spread (...) operator, which, when applied on an array, returns a list with the array elements.

Find the complete program on GitHub.

Python

Just like Perl and Node.js Python does have a push method, although they call it append. A pop method exists as well.

Python does have a min buildin, which can take an array as argument.

This leads to the following program:

import fileinput

stack = []
error = "Stack is empty"
for line in fileinput . input ():
    chunks  = line . split ()
    command = chunks [0]
    
    if command == "push":
        stack . append (int (chunks [1]))

    if command == "pop":
        if len (stack):
            stack . pop ()

    if command == "top":
        if len (stack):
            print stack [len (stack) - 1]
        else:
            print error

    if command == "min":
        if len (stack):
            print min (stack)
        else:
            print error

Find the complete program on GitHub.

AWK

AWK does not have a push operator. But it dynamically grows array, that is, if you add an element to an array, and the index doesn’t exist yet, AWK grows the array as needed. So we can simulate a push by just adding the pushed element to the first index after the largest current index.

To simulate pop, we make use of the delete function, which removes an element from an array.

There is no AWK buildin to get the minimum value of a list or array, so we have to iterate over the array, and find the minimum.

AWK programs automatically iterate over the input, executing blocks where preceding conditions are met:

BEGIN {error = "Stack is empty"}

{size = length (stack)}

A BEGIN block is executed once, before processing any input (if you are wondering where Perl got its BEGIN blocks from, the answer is AWK); this sets up an error message. The second block is executed for every line of input (there is no condition, which in AWK means, it’s always true). Here we store the current number of elements of the stack in the variable size, so we can refer to it in other blocks. Note that we do not have to declare variables.

Each of the four possible commands get their own block.

/^push/ {
    split($0, a, / +/)
    stack [size + 1] = a [2]
}

In AWK, the current line is in the variable $0. split works like split in Perl, but it has arguments in a different order. The first argument is the string to be split (here, the current line of input); the second argument is an array, in which the results are placed. The third argument is the pattern to split on. So, in the block, we split on whitespace, placing the command (which we already know is "push") in a [1], and the value to be pushed in a [2]. Note that in AWK, array indexes are 1-based.

We then assign the value to be pushed just passed the end of the current stack, in effect, pushing a value on the stack.

/^pop/  {
    delete stack [size]
}

Remove the last element of the array stack.

/^top/  {
    print size ? stack [size] : error
}

Print the last element of the array stack, or an error if the stack is empty.

/^min/  {
    if (size) {
        min = stack [1]
        for (i = 2; i <= size; i ++) {
            if (min > stack [i]) {
                min = stack [i]
            }
        }
        print min
    }
    else {
        print error
    }
}

Here we iterate over the array stack, finding the minimum value.

Find the complete program on GitHub.

C

As usual, C requires the most work. There are no push or pop operations, and arrays don’t automatically resize.

So, we will not be using an array. Instead, we will be using a linked list using records and pointers. Just like algorithms 101!

We will be using the following type and variable:

struct  node    {
    long          value;
    struct node * next;
};

struct node * stack = NULL;

Our stack is pointer to a record; this record holds two elements: value, and next, where the former is a value pushed on the stack, and the latter a pointer to another record. We initialize the stack to NULL, indicating the stack is empty.

We iterate over the input, putting each line into the variable line. Then, we do our actions:

        if (strncmp (line, "push", 4) == 0) {
            long val;
            if (sscanf (line + 4, " %ld", &val)) {
                struct node * head;
                head = (struct node *) malloc (sizeof (struct node));
                if (head == NULL) {
                    fprintf (stderr, "Out of memory!\n");
                    exit (1);
                }
                head -> value = val;
                head -> next  = stack;
                stack = head;
            }
        }

If we encounter a push command, we will be using sscanf to extract the value from the current line of input. We then create a new record by using malloc. In the new record, we set the just parsed value, and we let the new record point to the current stack. Finally, we update stack to point to the new record.

        if (strncmp (line, "pop", 3) == 0 && stack != NULL) {
            struct node * next;
            next = stack -> next;
            free (stack);
            stack = next;
        }

When we have to pop an element from the stack, we use a temporary variable next, which we set to the second element on the stack. We free stack, returning the memory, and then update stack.

        if (strncmp (line, "top", 3) == 0) {
            if (stack == NULL) {
                printf ("%s\n", error);
            }
            else {
                printf ("%ld\n", stack -> value);
            }
        }

This prints the top of the stack, or an error message if the stack is empty.

        if (strncmp (line, "min", 3) == 0) {
            if (stack == NULL) {
                printf ("%s\n", error);
            }
            else {
                long min = stack -> value;
                struct node * pointer = stack -> next;
                while (pointer != NULL) {
                    if (pointer -> value < min) {
                        min = pointer -> value;
                    }
                    pointer = pointer -> next;
                }
                printf ("%ld\n", min);
            }
        }

To find the minimum element of the stack, we have to walk through our linked list. Assuming the stack isn’t empty, we start with the top of the stack (first element of the linked list), and then walk the list by following the next pointer to the end. Each time we find an element which is less than the smallest element found so far, we remember it.

Find the complete program program on GitHub.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s