src/stack.c

   1 /*******************************************************************************
   2  * Reverse Polish Notation calculator.                                         *
   3  * Copyright (c) 2007-2008, Samuel Fredrickson <kinghajj@gmail.com>            *
   4  * All rights reserved.                                                        *
   5  *                                                                             *
   6  * Redistribution and use in source and binary forms, with or without          *
   7  * modification, are permitted provided that the following conditions are met: *
   8  *     * Redistributions of source code must retain the above copyright        *
   9  *       notice, this list of conditions and the following disclaimer.         *
  10  *     * Redistributions in binary form must reproduce the above copyright     *
  11  *       notice, this list of conditions and the following disclaimer in the   *
  12  *       documentation and/or other materials provided with the distribution.  *
  13  *                                                                             *
  14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER ``AS IS'' AND ANY EXPRESS *
  15  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED           *
  16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE      *
  17  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY        *
  18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES  *
  19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR          *
  20  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER  *
  21  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT          *
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY   *
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH *
  24  * DAMAGE.                                                                     *
  25  ******************************************************************************/
  26
  27 /*******************************************************************************
  28  * stack.c - implements the value stack.                                       *
  29  ******************************************************************************/
  30
  31 #include "rpn.h"
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34
  35 /**
  36  * Creates a new, empty stack.
  37  *
  38  * @return The new, empty stack.
  39  */
  40 RPNStack *RPN_newStack(RPNStack *next)
  41 {
  42         RPNStack *stack = new(RPNStack);
  43         if(!stack)
  44                 RPN_error("could not allocate memory for the stack.");
  45         stack->first = NULL;
  46         stack->next  = next;
  47         stack->len   = 0;
  48         RPN_dprintf("allocated stack %p", stack);
  49         return stack;
  50 }
  51
  52 /**
  53  * Creates a new node.
  54  * @param value The value of the node.
  55  *
  56  * @param next The next node in the stack.
  57  * @return The new node.
  58  */
  59 RPNNode *RPN_newNode(RPNValue value, RPNNode *next)
  60 {
  61         RPNNode *node = new(RPNNode);
  62         if(!node)
  63                 RPN_error("could not allocate memory for a stack node.");
  64         node->value = value;
  65         node->next  = next;
  66         RPN_dprintf("allocated node at %p to %p", node, next);
  67         return node;
  68 }
  69
  70 /**
  71  * Creates a deep copy of a node.
  72  *
  73  * @param node The node to copy.
  74  * @return A new node and its subnodes with the same values of the input node.
  75  */
  76 RPNNode *RPN_copyNode(RPNNode *node)
  77 {
  78         RPNNode *new_node = NULL;
  79
  80         if(node)
  81                 new_node = RPN_newNode(node->value, RPN_copyNode(node->next));
  82
  83         return new_node;
  84 }
  85
  86 /**
  87  * Creates a deep copy of the stack.
  88  *
  89  * @param stack The stack to copy.
  90  * @return A new stack with new nodes with the same values of the input stack.
  91  */
  92 RPNStack *RPN_copyStack(RPNStack *stack)
  93 {
  94         RPNStack *new_stack = NULL;
  95
  96         if(stack) {
  97                 new_stack = RPN_newStack(stack);
  98                 new_stack->first = RPN_copyNode(stack->first);
  99                 new_stack->len = stack->len;
 100         }
 101
 102         return new_stack;
 103 }
 104
 105 /**
 106  * Pushes a value to a stack.
 107  *
 108  * @param stack The stack.
 109  * @param value The value to push.
 110  * @return true if succeeds.
 111  */
 112 bool RPN_push(RPNStack *stack, RPNValue value)
 113 {
 114         if(!stack)
 115                 RPN_error("tried to push to a NULL stack.");
 116         RPNNode *node = RPN_newNode(value, stack->first);
 117         stack->first = node;
 118         stack->len++;
 119         RPN_dprintf("pushed " RPN_VALUE_SHORT_FORMAT  " to stack", value);
 120         return true;
 121 }
 122
 123 /**
 124  * Pops a value from a stack.
 125  *
 126  * @param stack The stack to pop.
 127  * @return The popped value.
 128  */
 129 RPNValue RPN_pop(RPNStack *stack)
 130 {
 131         RPNNode *popped;
 132         RPNValue value = 0;
 133
 134         if(!stack)
 135                 RPN_error("tried to pop from a NULL stack.");
 136         if(RPN_canOperate(stack, 1))
 137         {
 138                 // get node to pop
 139                 popped = stack->first;
 140                 value = popped->value;
 141                 // re-wire stack
 142                 stack->first = popped->next;
 143                 // free node
 144                 RPN_free(popped);
 145                 stack->len--;
 146                 RPN_dprintf("poped %x from stack", popped);
 147         }
 148
 149         return value;
 150 }
 151
 152 /**
 153  * Returns the topmost item of a stack.
 154  *
 155  * @param stack The stack.
 156  * @return The topmost item of the stack.
 157  */
 158 RPNValue RPN_peek(RPNStack *stack)
 159 {
 160         RPNValue value = 0;
 161
 162         if(!stack)
 163                 RPN_error("attempted to peek a NULL stack.");
 164
 165         if(RPN_canOperate(stack, 1))
 166                 value = stack->first->value;
 167
 168         return value;
 169 }
 170
 171 /**
 172  * Swaps the top two items of a stack.
 173  *
 174  * @param stack The stack.
 175  */
 176 void RPN_swap(RPNStack *stack)
 177 {
 178         RPNValue first, second;
 179
 180         if(RPN_canOperate(stack, 2))
 181         {
 182                 first  = RPN_pop(stack);
 183                 second = RPN_pop(stack);
 184                 RPN_push(stack, first);
 185                 RPN_push(stack, second);
 186         }
 187 }
 188
 189 /**
 190  * Frees a stack and all of its nodes.
 191  *
 192  * @param stack The stack to free.
 193  */
 194 void RPN_freeStack(RPNStack *stack)
 195 {
 196         RPNNode *node, *next;
 197
 198         if(stack) {
 199                 // free all nodes
 200                 for(node = stack->first; node; node = next)
 201                 {
 202                         next = node->next;
 203                         RPN_free(node);
 204                         RPN_dprintf("freed node %p", node);
 205                 }
 206
 207                 // free the stack
 208                 RPN_free(stack);
 209                 RPN_dprintf("freed stack %p", stack);
 210         }
 211 }
 212
 213 /**
 214  * Tests if the stack has at least a certain number of items.
 215  *
 216  * @param stack The stack to test.
 217  * @param nargs The number of required items.
 218  * @return true or false.
 219  */
 220 bool RPN_canOperate(RPNStack *stack, unsigned int nargs)
 221 {
 222         if(!stack)
 223                 RPN_error("tried to probe a NULL stack.");
 224
 225         RPN_dprintf("probing %p\n", stack);
 226
 227         // can only operate if there are enough items in the stack
 228         return stack->len >= nargs ? true : false;
 229 }
 230
 231 /**
 232  * Prints a stack.
 233  *
 234  * @param stack The stack.
 235  */
 236 void RPN_printStack(RPNStack *stack)
 237 {
 238         RPNNode *node;
 239
 240         RPN_printf("[ ");
 241         for(node = stack->first; node; node = node->next)
 242                 RPN_printf(RPN_VALUE_SHORT_FORMAT ", ", node->value);
 243         RPN_printf("]");
 244 }
 245
 246 /**
 247  * Prints a stack in more detail.
 248  *
 249  * @param stack The stack.
 250  */
 251 void RPN_printStackDetailed(RPNStack *stack)
 252 {
 253         RPNNode *node;
 254
 255         RPN_printf("[ ");
 256         for(node = stack->first; node; node = node->next)
 257                 RPN_printf(RPN_VALUE_LONG_FORMAT ", ", node->value);
 258         RPN_printf("]");
 259 }