stack – My Programming Notes

Tag Archives: stack

C++ || Simple Palindrome Checker Using A Stack & Queue Using C++

April 02, 2021 admin No comments

The following is a program which demonstrates how to use a stack and a queue to test for a palindrome using C++.

The program demonstrated on this page is an updated version of a previous program of the same type. This program is great practice for understanding how the two data structures work.

REQUIRED KNOWLEDGE FOR THIS PROGRAM

Template Classes - What Are They? Stacks Queues LIFO - Last In First Out FIFO - First In First Out

1. Overview

This program first asks the user to enter in text which they wish to compare for similarity. The data is then saved into the system using the “enqueue” and “push” functions available within the queue and stack classes. After the data is obtained, a while loop is used to iterate through both classes, checking to see if the characters at each location within both classes are the same. If the text within both classes are the same, it is a palindrome.

2. Palindrome Checker





		
		
			Palindrome Checker Using Stack & Queue
			
C++
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 22, 2012
//    Updated: Apr 2, 2021
//    Taken From: http://programmingnotes.org/
//    File:  palindrome.cpp
//    Description: Demonstrates a palindrome checker using a stack & queue
// ============================================================================
#include <iostream>
#include <cctype>
#include <string>
#include <queue>
#include <stack>

int main() {
    // Declare variables
    std::string text = "";
    bool isPalindrome = true;
    std::queue<char> queue;
    std::stack<char> stack;

    // Get data from user
    std::cout << "Enter in some text to see if its a palindrome: ";
    std::getline(std::cin, text);

    // Place the characters into the queue and stack for storage
    for (auto ch : text) {
        ch = std::toupper(ch);
        queue.push(ch);
        stack.push(ch);
    }

    // Determine if the string is a palindrome
    while (!queue.empty() && !stack.empty()) {
        if (queue.front() != stack.top()) {
            isPalindrome = false;
            break;
        }
        queue.pop();
        stack.pop();
    }

    // Display results to the screen
    std::cout << "\n\n" << text;
    if (isPalindrome) {
        std::cout << " is a palindrome!\n";
    } else {
        std::cout << " is NOT a palindrome..\n";
    }

    std::cin.get();
    return 0;
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 22, 2012
//    Updated: Apr 2, 2021
//    Taken From: http://programmingnotes.org/
//    File:  palindrome.cpp
//    Description: Demonstrates a palindrome checker using a stack & queue
// ============================================================================
#include <iostream>
#include <cctype>
#include <string>
#include <queue>
#include <stack>
 
int main() {
    // Declare variables
    std::string text = "";
    bool isPalindrome = true;
    std::queue<char> queue;
    std::stack<char> stack;
 
    // Get data from user
    std::cout << "Enter in some text to see if its a palindrome: ";
    std::getline(std::cin, text);
 
    // Place the characters into the queue and stack for storage
    for (auto ch : text) {
        ch = std::toupper(ch);
        queue.push(ch);
        stack.push(ch);
    }
 
    // Determine if the string is a palindrome
    while (!queue.empty() && !stack.empty()) {
        if (queue.front() != stack.top()) {
            isPalindrome = false;
            break;
        }
        queue.pop();
        stack.pop();
    }
 
    // Display results to the screen
    std::cout << "\n\n" << text;
    if (isPalindrome) {
        std::cout << " is a palindrome!\n";
    } else {
        std::cout << " is NOT a palindrome..\n";
    }
 
    std::cin.get();
    return 0;
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output:

====== RUN 1 ======
Enter in some text to see if its a palindrome: StEP on No pETS StEP on No pETS is a palindrome! ====== RUN 2 ====== Enter in some text to see if its a palindrome: Hello World Hello World is NOT a palindrome.. ====== RUN 3 ====== Enter in some text to see if its a palindrome: Kenneth, Jennifer, Lynn, Sole
Kenneth, Jennifer, Lynn, Sole is NOT a palindrome..

C++ || Snippet – Custom Template Linked List Sample Code

July 26, 2012 admin 1 Comment

This page will consist of sample code for a singly linked list, which is loosely based on the built in C++ “List” library. Provided in the linked list class are the following functions:





		
		
			* PushFront - Adds new item to the front of the list (LIFO)

* PushBack - Adds new item to the back of the list (FIFO)

* PopFront - Returns & removes first item from the list

* PopBack - Returns & removes last item from the list

* Front - Returns (but does not delete) the first item from the list

* Back - Returns (but does not delete) the last item from the list

* Delete - Searches and deletes the requested item

* Display - Display all the current contents in the list

* Replace - Replaces existing item from the list with a new item
            If existing item cannot be found, the new item is added to the back of the list

* InsertBefore - Inserts new item before the existing item. 
                If existing item cannot be found, the new item is added to the back of the list

* InsertAfter - Inserts new item after the existing item. 
                If existing item cannot be found, the new item is added to the back of the list

* InsertInOrder - Inserts new item in numerical order, from lowest to highest

* Size - Return the current size of the list

* MakeEmpty - Initializes the list to an empty state 
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
				
						* PushFront - Adds new item to the front of the list (LIFO)
 
* PushBack - Adds new item to the back of the list (FIFO)
 
* PopFront - Returns & removes first item from the list
 
* PopBack - Returns & removes last item from the list
 
* Front - Returns (but does not delete) the first item from the list
 
* Back - Returns (but does not delete) the last item from the list
 
* Delete - Searches and deletes the requested item
 
* Display - Display all the current contents in the list
 
* Replace - Replaces existing item from the list with a new item
            If existing item cannot be found, the new item is added to the back of the list
 
* InsertBefore - Inserts new item before the existing item. 
                If existing item cannot be found, the new item is added to the back of the list
 
* InsertAfter - Inserts new item after the existing item. 
                If existing item cannot be found, the new item is added to the back of the list
 
* InsertInOrder - Inserts new item in numerical order, from lowest to highest
 
* Size - Return the current size of the list
 
* MakeEmpty - Initializes the list to an empty state

From the following, the functions of interest to look out for are the “Delete, Display, Replace, InsertBefore, InsertAfter, and InsertInOrder” functions as they are typically used as programming assignments in many C++ Data structures courses to further demonstrate how linked lists operate.





		
		
			#include 'LinkedList.h'
			
C++
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 26, 2012
//    Taken From: http://programmingnotes.org/
//    File:  LinkedList.h
//    Description: This is a class which implements various functions which
//          demonstrates the use of a Linked List. 
// ============================================================================
#include <iostream>

template <class ItemType>
class LinkedList
{
public:
    LinkedList();
        /*   Function: Constructor initializes list 
            Precondition: None
            Postcondition: Defines private variables */
    bool IsEmpty();
        /*   Function: Determines whether queue is empty
            Precondition: List has been created
            Postcondition: The function = true if the list is empty and the
                             function = false if list is not empty */
    void PushFront(ItemType item);
        /*   Function: Adds new item to the front of the list (LIFO)
            Precondition:  List has been created and is not full
            Postcondition: Item is in the list */
    void PushBack(ItemType item);
        /*   Function: Adds new item to the back of the list (FIFO)
            Precondition:  List has been created and is not full
            Postcondition: Item is in the list */
    ItemType PopFront();
        /*   Function: Returns & removes first item from the last
            Precondition: List has been initialized
            Postcondition: The first item in the list is removed */
    ItemType PopBack();
        /*   Function: Returns & removes last item from the list
            Precondition: List has been initialized
            Postcondition: The last item in the list is removed */
    ItemType Front();
        /*   Function: Returns (but does not delete) the first item from the list
            Precondition: List has been initialized
            Postcondition: The first item in the list is removed */
    ItemType Back();
        /*   Function: Returns (but does not delete) the last item from the list
            Precondition: List has been initialized
            Postcondition: The last item in the list is removed */
    void Delete(ItemType item);
        /*   Function: Searches and deletes the requested item
            Precondition:  List has been created and is not empty
            Postcondition: Item removed from the list */
    void Display();
        /*   Function: Display all the current contents in the list
            Precondition:  List has been created and is not empty
            Postcondition: List is displayed to the screen */
    void Replace(ItemType initial, ItemType replace);
        /*   Function: Replaces existing item from the list with a new item
            Precondition:  List has been created and is not empty
            Postcondition: Initial item is replaced with the new one */
    void InsertBefore(ItemType initial, ItemType newItem);
        /*   Function: Inserts new item before the existing item
            Precondition:  List has been created and is not empty
            Postcondition: New item is inserted before the existing item */
    void InsertAfter(ItemType initial, ItemType newItem);
        /*   Function: Inserts new item after the existing item
            Precondition:  List has been created and is not empty
            Postcondition: New item is inserted after the existing item */
    void InsertInOrder(ItemType item);  
        /*   Function: Inserts new item in numerical order, from lowest to highest
            Precondition:  List has been created and is not empty
            Postcondition: The list is sorted in numerical order */
    int Size();
        /*   Function: Return the current size of the list
            Precondition: List has been initialized
            Postcondition: The size of the list is returned */
    void MakeEmpty();
        /*   Function: Initializes the list to an empty state 
            Precondition: List has been created
            Postcondition: List no longer exists */
    ~LinkedList();
        /*   Function: Deletes all the items in the list
            Precondition: List has been declared
            Postcondition: List no longer exists */

private:
    struct node
    {
        ItemType info;
        node* next;
    };
    node* head; 
    int size;
};

//=========================  Implementation  ================================//

template <class ItemType>
LinkedList<ItemType>::LinkedList()
{
    head = NULL;
    size = 0;
}// end of LinkedList

template <class ItemType>
bool LinkedList<ItemType>::IsEmpty()
{
    return (head==NULL);
}// end of IsEmpty

template <class ItemType>
void LinkedList<ItemType>::PushFront(ItemType item)
{
    // LIFO 
    node* temp = new node;
    temp-> info = item;
    temp-> next = head;
    head = temp;
    ++size;
}// end of PushFront

template <class ItemType>
void LinkedList<ItemType>::PushBack(ItemType item)
{
    // FIFO
    node* temp = new node;
    temp->info = item;
    temp->next = NULL;
    
    if(IsEmpty())
    {
        head=temp;
    }
    else
    {
        node* temp2 = head;        
        while(temp2->next!=NULL)
        {
            temp2=temp2->next;
        }
        temp2->next=temp;
    }
    ++size;
}// end of PushBack

template <class ItemType>
ItemType LinkedList<ItemType>::PopFront()
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    else
    {  
        ItemType item = head-> info;  
        node* temp = head;
        head = head-> next;
        delete temp;
        --size;
        return item;
    }
}// end of PopFront

template <class ItemType>
ItemType LinkedList<ItemType>::PopBack()
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    else if(size == 1)
    {
        ItemType item = PopFront();
        return item;
    }
    else
    {
        node* temp = head;
        ItemType item;
        while(temp->next != NULL)
        {
            if(temp->next->next==NULL)
            {
                node* temp2=temp->next;
                temp->next=temp->next->next;
                item = temp2-> info;
                delete temp2;
                break;
            }
            temp=temp->next;
        }
        --size;
        return item;
    }   
}// end of PopBack

template <class ItemType>
ItemType LinkedList<ItemType>::Front()
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    else
    { 
        return head-> info;
    }
}// end of Front

template <class ItemType>
ItemType LinkedList<ItemType>::Back() 
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    else
    {
        node* temp = head; 
        while(temp->next != NULL)
        {
            temp = temp-> next;
        }
        ItemType item = temp-> info;
        return item;
    }   
}// end of Back

template <class ItemType>
void LinkedList<ItemType>::Delete(ItemType item)
{
    node* temp=head;
    if(IsEmpty())
    {
        return;
    }
    else if(temp->info==item)
    {
        head=head->next;
        delete temp;
        --size;
    }
    else
    {
        while(temp->next!=NULL)
        {
            if(temp->next->info==item)
            {
                node* temp2=temp->next;
                temp->next=temp->next->next;
                delete temp2;
                --size;
                break;
            }
            temp=temp->next;
        }
    }
}// end of Delete

template <class ItemType>
void LinkedList<ItemType>::Display()
{
    node* temp=head;
    while(temp!=NULL)
    {
        std::cout<<temp->info<<std::endl;
        temp=temp->next;
    }
}// end of Display

template <class ItemType>
void LinkedList<ItemType>::Replace(ItemType initial, ItemType replace)
{
    node* temp=head;
    if(IsEmpty())
    {
        PushFront(replace);
    }
    else if(temp->info==initial)
    {
        temp->info=replace;
    }
    else
    {        
        while(temp->next!=NULL)
        {
            if(temp->info==initial)
            {
                temp->info=replace;
                break;
            }
            temp=temp->next;
        }
        if(temp->next==NULL)
        {
            PushBack(replace);
        }
    }
}// end of Replace

template <class ItemType>
void LinkedList<ItemType>::InsertBefore(ItemType initial, ItemType newItem)
{
    node* temp=head;
    node* temp2=new node;
    temp2->info=initial;
    temp2->next=NULL;     
    
    if(IsEmpty())
    {
        PushFront(newItem);
    }
    else if(temp->info==initial)
    {
        temp->info=newItem; 
        temp2->next=temp->next;
        temp->next=temp2;
        ++size;
    }
    else
    {
        while(temp->next!=NULL)
        {
            if(temp->info==initial)
            {
                temp->info=newItem; 
                temp2->next=temp->next;
                temp->next=temp2;
                ++size;
                break;
            }
            temp=temp->next;           
        }
        if(temp->next==NULL)
        {
            PushBack(newItem);
        }
    }
}// end of InsertBefore

template <class ItemType>
void LinkedList<ItemType>::InsertAfter(ItemType initial, ItemType newItem)
{
    node* temp=head;
    node* temp2=new node;
    temp2->info=newItem;
    temp2->next=NULL;
    
    if(IsEmpty())
    {
        PushFront(newItem);
    }
    else if(temp->info==initial)
    {
        temp2->next=temp->next;
        temp->next=temp2;
        ++size;
    }
    else
    {   
        while(temp->next!=NULL)
        {
            if(temp->info==initial)
            {
                temp2->next=temp->next;
                temp->next=temp2;
                ++size;
                break;
            }
            temp=temp->next;
        }
        if(temp->next==NULL)
        {
            PushBack(newItem);
        }
    }
}// end of InsertAfter

template <class ItemType>
void LinkedList<ItemType>::InsertInOrder(ItemType item)
{
    if(IsEmpty())
    {
        PushFront(item);
    }
    else
    {
        node* temp=head;
        node* temp2=new node;
    
        if(item <=(temp->info))
        {  
            ItemType placeHolder=temp->info;
            temp2->info=placeHolder;
            temp->info=item;
            temp2->next=temp->next;
            temp->next=temp2;
            ++size;
        } 
        else
        {
            while(temp->next!=NULL)
            {       
                if(((temp->info) <= item) && (item <= (temp->next->info)))
                {           
                    temp2->info=item;
                    temp2->next=temp->next;
                    temp->next=temp2;
                    ++size;
                    return;
                }
                temp=temp->next;
            }
            if(temp->next==NULL)
            {
                PushBack(item);
            }
        }
    }
}// end of InsertInOrder

template <class ItemType>
int LinkedList<ItemType>::Size()
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    return size;
}// end of Size 

template <class ItemType>
void LinkedList<ItemType>::MakeEmpty()
{
    if(!IsEmpty())
    {
        std::cout << "\nDestroying nodes...\n";
        while(!IsEmpty())
        {
            node* temp = head;
            //std::cout << temp-> info << '\n';
            head = head-> next;
            delete temp;
        }
        size = 0;
    }
}// end of MakeEmpty

template <class ItemType>
LinkedList<ItemType>::~LinkedList()
{
    MakeEmpty();
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 26, 2012
//    Taken From: http://programmingnotes.org/
//    File:  LinkedList.h
//    Description: This is a class which implements various functions which
//          demonstrates the use of a Linked List. 
// ============================================================================
#include <iostream>
 
template <class ItemType>
class LinkedList
{
public:
    LinkedList();
        /*   Function: Constructor initializes list 
            Precondition: None
            Postcondition: Defines private variables */
    bool IsEmpty();
        /*   Function: Determines whether queue is empty
            Precondition: List has been created
            Postcondition: The function = true if the list is empty and the
                             function = false if list is not empty */
    void PushFront(ItemType item);
        /*   Function: Adds new item to the front of the list (LIFO)
            Precondition:  List has been created and is not full
            Postcondition: Item is in the list */
    void PushBack(ItemType item);
        /*   Function: Adds new item to the back of the list (FIFO)
            Precondition:  List has been created and is not full
            Postcondition: Item is in the list */
    ItemType PopFront();
        /*   Function: Returns & removes first item from the last
            Precondition: List has been initialized
            Postcondition: The first item in the list is removed */
    ItemType PopBack();
        /*   Function: Returns & removes last item from the list
            Precondition: List has been initialized
            Postcondition: The last item in the list is removed */
    ItemType Front();
        /*   Function: Returns (but does not delete) the first item from the list
            Precondition: List has been initialized
            Postcondition: The first item in the list is removed */
    ItemType Back();
        /*   Function: Returns (but does not delete) the last item from the list
            Precondition: List has been initialized
            Postcondition: The last item in the list is removed */
    void Delete(ItemType item);
        /*   Function: Searches and deletes the requested item
            Precondition:  List has been created and is not empty
            Postcondition: Item removed from the list */
    void Display();
        /*   Function: Display all the current contents in the list
            Precondition:  List has been created and is not empty
            Postcondition: List is displayed to the screen */
    void Replace(ItemType initial, ItemType replace);
        /*   Function: Replaces existing item from the list with a new item
            Precondition:  List has been created and is not empty
            Postcondition: Initial item is replaced with the new one */
    void InsertBefore(ItemType initial, ItemType newItem);
        /*   Function: Inserts new item before the existing item
            Precondition:  List has been created and is not empty
            Postcondition: New item is inserted before the existing item */
    void InsertAfter(ItemType initial, ItemType newItem);
        /*   Function: Inserts new item after the existing item
            Precondition:  List has been created and is not empty
            Postcondition: New item is inserted after the existing item */
    void InsertInOrder(ItemType item);  
        /*   Function: Inserts new item in numerical order, from lowest to highest
            Precondition:  List has been created and is not empty
            Postcondition: The list is sorted in numerical order */
    int Size();
        /*   Function: Return the current size of the list
            Precondition: List has been initialized
            Postcondition: The size of the list is returned */
    void MakeEmpty();
        /*   Function: Initializes the list to an empty state 
            Precondition: List has been created
            Postcondition: List no longer exists */
    ~LinkedList();
        /*   Function: Deletes all the items in the list
            Precondition: List has been declared
            Postcondition: List no longer exists */
 
private:
    struct node
    {
        ItemType info;
        node* next;
    };
    node* head; 
    int size;
};
 
//=========================  Implementation  ================================//
 
template <class ItemType>
LinkedList<ItemType>::LinkedList()
{
    head = NULL;
    size = 0;
}// end of LinkedList
 
template <class ItemType>
bool LinkedList<ItemType>::IsEmpty()
{
    return (head==NULL);
}// end of IsEmpty
 
template <class ItemType>
void LinkedList<ItemType>::PushFront(ItemType item)
{
    // LIFO 
    node* temp = new node;
    temp-> info = item;
    temp-> next = head;
    head = temp;
    ++size;
}// end of PushFront
 
template <class ItemType>
void LinkedList<ItemType>::PushBack(ItemType item)
{
    // FIFO
    node* temp = new node;
    temp->info = item;
    temp->next = NULL;
    
    if(IsEmpty())
    {
        head=temp;
    }
    else
    {
        node* temp2 = head;        
        while(temp2->next!=NULL)
        {
            temp2=temp2->next;
        }
        temp2->next=temp;
    }
    ++size;
}// end of PushBack
 
template <class ItemType>
ItemType LinkedList<ItemType>::PopFront()
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    else
    {  
        ItemType item = head-> info;  
        node* temp = head;
        head = head-> next;
        delete temp;
        --size;
        return item;
    }
}// end of PopFront
 
template <class ItemType>
ItemType LinkedList<ItemType>::PopBack()
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    else if(size == 1)
    {
        ItemType item = PopFront();
        return item;
    }
    else
    {
        node* temp = head;
        ItemType item;
        while(temp->next != NULL)
        {
            if(temp->next->next==NULL)
            {
                node* temp2=temp->next;
                temp->next=temp->next->next;
                item = temp2-> info;
                delete temp2;
                break;
            }
            temp=temp->next;
        }
        --size;
        return item;
    }   
}// end of PopBack
 
template <class ItemType>
ItemType LinkedList<ItemType>::Front()
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    else
    { 
        return head-> info;
    }
}// end of Front
 
template <class ItemType>
ItemType LinkedList<ItemType>::Back() 
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    else
    {
        node* temp = head; 
        while(temp->next != NULL)
        {
            temp = temp-> next;
        }
        ItemType item = temp-> info;
        return item;
    }   
}// end of Back
 
template <class ItemType>
void LinkedList<ItemType>::Delete(ItemType item)
{
    node* temp=head;
    if(IsEmpty())
    {
        return;
    }
    else if(temp->info==item)
    {
        head=head->next;
        delete temp;
        --size;
    }
    else
    {
        while(temp->next!=NULL)
        {
            if(temp->next->info==item)
            {
                node* temp2=temp->next;
                temp->next=temp->next->next;
                delete temp2;
                --size;
                break;
            }
            temp=temp->next;
        }
    }
}// end of Delete
 
template <class ItemType>
void LinkedList<ItemType>::Display()
{
    node* temp=head;
    while(temp!=NULL)
    {
        std::cout<<temp->info<<std::endl;
        temp=temp->next;
    }
}// end of Display
 
template <class ItemType>
void LinkedList<ItemType>::Replace(ItemType initial, ItemType replace)
{
    node* temp=head;
    if(IsEmpty())
    {
        PushFront(replace);
    }
    else if(temp->info==initial)
    {
        temp->info=replace;
    }
    else
    {        
        while(temp->next!=NULL)
        {
            if(temp->info==initial)
            {
                temp->info=replace;
                break;
            }
            temp=temp->next;
        }
        if(temp->next==NULL)
        {
            PushBack(replace);
        }
    }
}// end of Replace
 
template <class ItemType>
void LinkedList<ItemType>::InsertBefore(ItemType initial, ItemType newItem)
{
    node* temp=head;
    node* temp2=new node;
    temp2->info=initial;
    temp2->next=NULL;     
    
    if(IsEmpty())
    {
        PushFront(newItem);
    }
    else if(temp->info==initial)
    {
        temp->info=newItem; 
        temp2->next=temp->next;
        temp->next=temp2;
        ++size;
    }
    else
    {
        while(temp->next!=NULL)
        {
            if(temp->info==initial)
            {
                temp->info=newItem; 
                temp2->next=temp->next;
                temp->next=temp2;
                ++size;
                break;
            }
            temp=temp->next;           
        }
        if(temp->next==NULL)
        {
            PushBack(newItem);
        }
    }
}// end of InsertBefore
 
template <class ItemType>
void LinkedList<ItemType>::InsertAfter(ItemType initial, ItemType newItem)
{
    node* temp=head;
    node* temp2=new node;
    temp2->info=newItem;
    temp2->next=NULL;
    
    if(IsEmpty())
    {
        PushFront(newItem);
    }
    else if(temp->info==initial)
    {
        temp2->next=temp->next;
        temp->next=temp2;
        ++size;
    }
    else
    {   
        while(temp->next!=NULL)
        {
            if(temp->info==initial)
            {
                temp2->next=temp->next;
                temp->next=temp2;
                ++size;
                break;
            }
            temp=temp->next;
        }
        if(temp->next==NULL)
        {
            PushBack(newItem);
        }
    }
}// end of InsertAfter
 
template <class ItemType>
void LinkedList<ItemType>::InsertInOrder(ItemType item)
{
    if(IsEmpty())
    {
        PushFront(item);
    }
    else
    {
        node* temp=head;
        node* temp2=new node;
    
        if(item <=(temp->info))
        {  
            ItemType placeHolder=temp->info;
            temp2->info=placeHolder;
            temp->info=item;
            temp2->next=temp->next;
            temp->next=temp2;
            ++size;
        } 
        else
        {
            while(temp->next!=NULL)
            {       
                if(((temp->info) <= item) && (item <= (temp->next->info)))
                {           
                    temp2->info=item;
                    temp2->next=temp->next;
                    temp->next=temp2;
                    ++size;
                    return;
                }
                temp=temp->next;
            }
            if(temp->next==NULL)
            {
                PushBack(item);
            }
        }
    }
}// end of InsertInOrder
 
template <class ItemType>
int LinkedList<ItemType>::Size()
{
    if(IsEmpty())
    {
        std::cout<<"\nLIST EMPTY\n";
    }
    return size;
}// end of Size 
 
template <class ItemType>
void LinkedList<ItemType>::MakeEmpty()
{
    if(!IsEmpty())
    {
        std::cout << "\nDestroying nodes...\n";
        while(!IsEmpty())
        {
            node* temp = head;
            //std::cout << temp-> info << '\n';
            head = head-> next;
            delete temp;
        }
        size = 0;
    }
}// end of MakeEmpty
 
template <class ItemType>
LinkedList<ItemType>::~LinkedList()
{
    MakeEmpty();
}// http://programmingnotes.org/

===== DEMONSTRATION HOW TO USE =====

Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.





		
		
			How To Use #include 'LinkedList.h'
			
C++
			
			#include <iostream>
#include <string>
#include "LinkedList.h"
using namespace std;

int main()
{
    // declare variables, using a string as
    // the item type for the class. 

    // NOTE: you can also use an int, float, double etc.
    // instead of a string
    LinkedList<string> list;

    // demontrate the "InOrder" function
    cout<<"** These are names of fruits sorted in order"
        <<" using the 'InsertInOrder()' function:\n\n";
    list.InsertInOrder("Tomato");
    list.InsertInOrder("Orange");
    list.InsertInOrder("Apple");
    list.InsertInOrder("Plum");
    list.Display();

    cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";

    // demonstrate the "Delete" function
    cout<<"\n** Here is the same list with the word 'Plum' deleted"
        << "\nusing the 'Delete()' function:\n\n";
    list.Delete("Plum");
    list.Display();

    cout<<"\nThere is currently "<<list.Size()<<" items in the listnn";

    // demonstrate the "InsertAfter" function
    cout<<"\n** Now the word 'Bike' will be added to the list,"
        <<"\nright after the word 'Apple' using the "
        <<"'InsertAfter()' function:\n\n";
    list.InsertAfter("Apple","Bike");
    list.Display();

    cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";

    // demonstrate the "InsertBefore" function
    cout<<"\n** Now the name 'Jessica' will be added to the list,"
        <<"\nright before the word 'Orange' using the "
        <<"'InsertBefore()' function:\n\n";
    list.InsertBefore("Orange","Jessica");
    list.Display();

    cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";

    // demonstrate the "Replace" function
    cout<<"\n** The word 'Orange' will now be replaced with the name,"
        <<"\n'Kat' using the 'Replace()' function:\n\n";
    list.Replace("Orange","Kat");
    list.Display();

    cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
				
						#include <iostream>
#include <string>
#include "LinkedList.h"
using namespace std;
 
int main()
{
    // declare variables, using a string as
    // the item type for the class. 
 
    // NOTE: you can also use an int, float, double etc.
    // instead of a string
    LinkedList<string> list;
 
    // demontrate the "InOrder" function
    cout<<"** These are names of fruits sorted in order"
        <<" using the 'InsertInOrder()' function:\n\n";
    list.InsertInOrder("Tomato");
    list.InsertInOrder("Orange");
    list.InsertInOrder("Apple");
    list.InsertInOrder("Plum");
    list.Display();
 
    cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";
 
    // demonstrate the "Delete" function
    cout<<"\n** Here is the same list with the word 'Plum' deleted"
        << "\nusing the 'Delete()' function:\n\n";
    list.Delete("Plum");
    list.Display();
 
    cout<<"\nThere is currently "<<list.Size()<<" items in the listnn";
 
    // demonstrate the "InsertAfter" function
    cout<<"\n** Now the word 'Bike' will be added to the list,"
        <<"\nright after the word 'Apple' using the "
        <<"'InsertAfter()' function:\n\n";
    list.InsertAfter("Apple","Bike");
    list.Display();
 
    cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";
 
    // demonstrate the "InsertBefore" function
    cout<<"\n** Now the name 'Jessica' will be added to the list,"
        <<"\nright before the word 'Orange' using the "
        <<"'InsertBefore()' function:\n\n";
    list.InsertBefore("Orange","Jessica");
    list.Display();
 
    cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";
 
    // demonstrate the "Replace" function
    cout<<"\n** The word 'Orange' will now be replaced with the name,"
        <<"\n'Kat' using the 'Replace()' function:\n\n";
    list.Replace("Orange","Kat");
    list.Display();
 
    cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";
}// http://programmingnotes.org/

Once compiled, you should get this as your output

** These are names of fruits sorted in order using the 'InsertInOrder()' function:
Apple Orange Plum Tomato There is currently 4 items in the list ** Here is the same list with the word 'Plum' deleted using the 'Delete()' function: Apple Orange Tomato There is currently 3 items in the list ** Now the word 'Bike' will be added to the list, right after the word 'Apple' using the 'InsertAfter()' function: Apple Bike Orange Tomato There is currently 4 items in the list ** Now the name 'Jessica' will be added to the list, right before the word 'Orange' using the 'InsertBefore()' function: Apple Bike Jessica Orange Tomato There is currently 5 items in the list ** The word 'Orange' will now be replaced with the name, 'Kat' using the 'Replace()' function: Apple Bike Jessica Kat Tomato
There is currently 5 items in the list

C++ || Snippet – Palindrome Checker Using A Stack & Queue

July 22, 2012 admin No comments

Click Here For Updated Version Of Program

This page consists of a sample program which demonstrates how to use a stack and a queue to test for a palindrome. This program is great practice for understanding how the two data structures work.

REQUIRED KNOWLEDGE FOR THIS PROGRAM

Structs Classes Template Classes - What Are They? Stacks Queues LIFO - Last In First Out FIFO - First In First Out #include 'SingleQueue.h' #include 'ClassStackListType.h'

NOTE: This program uses two custom template.h classes. To obtain the code for both class, click here and here.





		
		
			Palindrome Checker Using Stack & Queue
			
C++
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 22, 2012
//    Taken From: http://programmingnotes.org/
//    File:  palindrome.cpp
//    Description: Demonstrates a palindrome checker using a stack & queue
// ============================================================================
#include <iostream>
#include <cctype>
#include "SingleQueue.h"
#include "ClassStackListType.h"
using namespace std;

int main()
{
    // declare variable
    char singleChar = ' ';
    bool isPalindrome = true;
    SingleQueue<char> queue;
    StackListType<char> stack;

    // get data from user, then place them into the
    // queue and stack for storage. This loop also
    // displays the user input back to the screen via cout
    cout <<"Enter in some text to see if its a palindrome: ";
    while(cin.get(singleChar) && singleChar != '\n')
    {
        cout<<singleChar;
        queue.EnQueue(toupper(singleChar));
        stack.Push(toupper(singleChar));
    }

    // determine if the string is a palindrome
    while((!queue.IsEmpty() && !stack.IsEmpty())
        && isPalindrome)
    {
        if(queue.Front() != stack.Top())
        {
            isPalindrome = false;
        }
        else
        {
            queue.DeQueue();
            stack.Pop();
        }
    }

    // display results to the screen
    if(isPalindrome)
    {
        cout<<" is a palindrome!\n";
    }
    else
    {
        cout<<" is NOT a palindrome..\n";
    }

    return 0;
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 22, 2012
//    Taken From: http://programmingnotes.org/
//    File:  palindrome.cpp
//    Description: Demonstrates a palindrome checker using a stack & queue
// ============================================================================
#include <iostream>
#include <cctype>
#include "SingleQueue.h"
#include "ClassStackListType.h"
using namespace std;
 
int main()
{
    // declare variable
    char singleChar = ' ';
    bool isPalindrome = true;
    SingleQueue<char> queue;
    StackListType<char> stack;
 
    // get data from user, then place them into the
    // queue and stack for storage. This loop also
    // displays the user input back to the screen via cout
    cout <<"Enter in some text to see if its a palindrome: ";
    while(cin.get(singleChar) && singleChar != '\n')
    {
        cout<<singleChar;
        queue.EnQueue(toupper(singleChar));
        stack.Push(toupper(singleChar));
    }
 
    // determine if the string is a palindrome
    while((!queue.IsEmpty() && !stack.IsEmpty())
        && isPalindrome)
    {
        if(queue.Front() != stack.Top())
        {
            isPalindrome = false;
        }
        else
        {
            queue.DeQueue();
            stack.Pop();
        }
    }
 
    // display results to the screen
    if(isPalindrome)
    {
        cout<<" is a palindrome!\n";
    }
    else
    {
        cout<<" is NOT a palindrome..\n";
    }
 
    return 0;
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output
(Note: The code was compiled 2 separate times to demonstrate different output)

====== RUN 1 ======
Enter in some text to see if its a palindrome: StEP on No pETS StEP on No pETS is a palindrome! ====== RUN 2 ====== Enter in some text to see if its a palindrome: Hello World
Hello World is NOT a palindrome..

C++ || Stack – Using A Stack, Determine If A Set Of Parentheses Is Well-Formed

May 14, 2012 admin 2 Comments

Here is another homework assignment which was presented in a C++ Data Structures course. This assignment was used to introduce the stack ADT, and helped prepare our class for two later assignments which required using a stack. Those assignments can be found here:

(1) Stack Based Infix To Postfix Conversion (Single Digit) (2) Stack Based Postfix Evaluation (Single Digit)

REQUIRED KNOWLEDGE FOR THIS PROGRAM

Stack Data Structure Cin.getline #include "ClassStackListType.h"

A simple exercise for testing a stack is determining whether a set of parenthesis is “well formed” or not. What exactly is meant by that? In the case of a pair of parenthesis, for an expression to be well formed, consider the following table.





		
		
			Well-Formed Expressions             |           Ill-Formed Expressions
------------------------------------|--------------------------------------
( a b c [ ] )                       |             ( a b c [ )
( ) [ ] { }                         |             ( (
{ ( a b c d e ) ( ) }               |             [ a b c d e ) ( ) }
( a + [ b - c ] / d )               |             ( a + [ b - c } /  d )
			
				
					
				
					1
2
3
4
5
6
				
						Well-Formed Expressions             |           Ill-Formed Expressions
------------------------------------|--------------------------------------
( a b c [ ] )                       |             ( a b c [ )
( ) [ ] { }                         |             ( (
{ ( a b c d e ) ( ) }               |             [ a b c d e ) ( ) }
( a + [ b - c ] / d )               |             ( a + [ b - c } /  d )

Given an expression with characters and parenthesis, ( ), [ ], and { }, our class was asked to determine if an expression was well formed or not by using the following algorithm:





		
		
			// An algorithm for a Well Formed expression

Set 'balanced' to true
Set 'symbol' to the first character in the current expression

while(there are more characters AND 'balanced' == true)
{
    if('symbol' is an opening symbol)
    {
        Push 'symbol' onto the stack
    }
    else if('symbol' is a closing symbol)
    {
        if the stack is empty
            'balanced' = false
        else
            Set the 'openSymbol' to the item at the top of the stack
            Pop the stack
            Check to see if 'symbol' matches 'openSymbol'
            (i.e - if openSymbol == '(' and symbol == ')'
            then 'balanced' = true)
    }
    Set 'symbol' to the next character in the current expression
}

if('balanced' == true AND stack is empty)
{
    Expression is well formed
}
else
{
    Expression is NOT well formed
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
				
						// An algorithm for a Well Formed expression
 
Set 'balanced' to true
Set 'symbol' to the first character in the current expression
 
while(there are more characters AND 'balanced' == true)
{
    if('symbol' is an opening symbol)
    {
        Push 'symbol' onto the stack
    }
    else if('symbol' is a closing symbol)
    {
        if the stack is empty
            'balanced' = false
        else
            Set the 'openSymbol' to the item at the top of the stack
            Pop the stack
            Check to see if 'symbol' matches 'openSymbol'
            (i.e - if openSymbol == '(' and symbol == ')'
            then 'balanced' = true)
    }
    Set 'symbol' to the next character in the current expression
}
 
if('balanced' == true AND stack is empty)
{
    Expression is well formed
}
else
{
    Expression is NOT well formed
}// http://programmingnotes.org/

======= WELL-FORMED EXPRESSIONS =======

This program uses a custom template.h class. To obtain the code for that class, click here.





		
		
			Is The Expression Well-Formed?
			
C++
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 14, 2012
//    Taken From: http://programmingnotes.org/
//    File:  wellFormed.cpp
//    Description: Demonstrates how to check if an expression is well formed
// ============================================================================
#include <iostream>
#include "ClassStackListType.h"
using namespace std;

// function prototypes
bool IsOpen(char symbol);
bool IsClosed(char symbol);
bool IsWellFormed(char openSymbol, char closeSymbol);

int main()
{
    // declare variables
    char expression[120];
    char openSymbol;
    int index=0;
    bool balanced = true;
    StackListType<char> stack; // this is the stack declaration

    // obtain data from the user using a char array
    cout <<"Enter an expression and press ENTER. "<<endl;
    cin.getline(expression,sizeof(expression));

    cout << "\nThe expression: " << expression;

    // loop thru the char array until we reach the 'NULL' character
    // and while 'balanced' == true
    while (expression[index]!='\0' && balanced)
    {
        // if input is an "open bracket" push onto stack
        // else, process info
        if (IsOpen(expression[index]))
        {
            stack.Push(expression[index]);
        }
        else if (IsClosed(expression[index]))
        {
            if(stack.IsEmpty())
            {
                balanced = false;
            }
            else
            {
                openSymbol = stack.Top();
                stack.Pop();
                balanced = IsWellFormed(openSymbol, expression[index]);
            }
        }
        ++index;
    }

    if (balanced && stack.IsEmpty())
    {
        cout << " is well formed..." << endl;
    }
    else
    {
        cout << " is NOT well formed!!! " << endl;
    }
}// End of Main

bool IsOpen(char symbol)
{
    if ((symbol == '(') || (symbol == '{') || (symbol == '['))
    {
        return true;
    }
    else
    {
        return false;
    }
}// End of IsOpen

bool IsClosed(char symbol)
{
    if ((symbol == ')') || (symbol == '}') || (symbol == ']'))
    {
        return true;
    }
    else
    {
        return false;
    }
}// End of IsClosed

bool IsWellFormed(char openSymbol, char closeSymbol)
{
    return (((openSymbol == '(') && closeSymbol == ')') || ((openSymbol == '{') && closeSymbol == '}')
        || ((openSymbol == '[') && closeSymbol == ']'));
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 14, 2012
//    Taken From: http://programmingnotes.org/
//    File:  wellFormed.cpp
//    Description: Demonstrates how to check if an expression is well formed
// ============================================================================
#include <iostream>
#include "ClassStackListType.h"
using namespace std;
 
// function prototypes
bool IsOpen(char symbol);
bool IsClosed(char symbol);
bool IsWellFormed(char openSymbol, char closeSymbol);
 
int main()
{
    // declare variables
    char expression[120];
    char openSymbol;
    int index=0;
    bool balanced = true;
    StackListType<char> stack; // this is the stack declaration
 
    // obtain data from the user using a char array
    cout <<"Enter an expression and press ENTER. "<<endl;
    cin.getline(expression,sizeof(expression));
 
    cout << "\nThe expression: " << expression;
 
    // loop thru the char array until we reach the 'NULL' character
    // and while 'balanced' == true
    while (expression[index]!='\0' && balanced)
    {
        // if input is an "open bracket" push onto stack
        // else, process info
        if (IsOpen(expression[index]))
        {
            stack.Push(expression[index]);
        }
        else if (IsClosed(expression[index]))
        {
            if(stack.IsEmpty())
            {
                balanced = false;
            }
            else
            {
                openSymbol = stack.Top();
                stack.Pop();
                balanced = IsWellFormed(openSymbol, expression[index]);
            }
        }
        ++index;
    }
 
    if (balanced && stack.IsEmpty())
    {
        cout << " is well formed..." << endl;
    }
    else
    {
        cout << " is NOT well formed!!! " << endl;
    }
}// End of Main
 
bool IsOpen(char symbol)
{
    if ((symbol == '(') || (symbol == '{') || (symbol == '['))
    {
        return true;
    }
    else
    {
        return false;
    }
}// End of IsOpen
 
bool IsClosed(char symbol)
{
    if ((symbol == ')') || (symbol == '}') || (symbol == ']'))
    {
        return true;
    }
    else
    {
        return false;
    }
}// End of IsClosed
 
bool IsWellFormed(char openSymbol, char closeSymbol)
{
    return (((openSymbol == '(') && closeSymbol == ')') || ((openSymbol == '{') && closeSymbol == '}')
        || ((openSymbol == '[') && closeSymbol == ']'));
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output
(Note: the code was compile four separate times to display different output)

====== RUN 1 ======
Enter an expression and press ENTER. (( The expression: (( is NOT well formed!!! ====== RUN 2 ====== Enter an expression and press ENTER. (a{b[]}c) The expression: (a{b[]}c) is well formed... ====== RUN 3 ====== Enter an expression and press ENTER. [(7 * 28) - 1987] The expression: [(7 * 28) - 1987] is well formed... ====== RUN 4 ====== Enter an expression and press ENTER. {3 + [2 / 3] - (9 + 18) * 12)
The expression: {3 + [2 / 3] - (9 + 18) * 12) is NOT well formed!!!

C++ || Snippet – Linked List Custom Template Stack Sample Code

April 09, 2012 admin No comments

This page will consist of sample code for a custom linked list template stack. This page differs from the previously highlighted array based template stack in that this version uses a singly linked list to store data rather than using an array.

Looking for sample code for a queue? Click here.

REQUIRED KNOWLEDGE FOR THIS SNIPPET

Structs Classes Template Classes - What Are They? Stacks LIFO - What Is It? #include < stack> Linked Lists - How To Use

This template class is a custom duplication of the Standard Template Library (STL) stack class. Whether you like building your own data structures, you simply do not like to use any inbuilt functions, opting to build everything yourself, or your homework requires you make your own data structure, this sample code is really useful. I feel its beneficial building functions such as this, that way you better understand the behind the scene processes.





		
		
			#include 'ClassStackListType.h'
			
C++
			
			// ============================================================================
//    Author: K Perkins
//    Date:   Apr 9, 2012
//    Taken From: http://programmingnotes.org/
//    File:  ClassStackListType.h
//    Description: This is a class which implements various functions
//          demonstrating the use of a stack. 
// ============================================================================
#include <iostream>         

template <class ItemType>
class StackListType
{
public:
    StackListType();
          /*   Function: constructor initializes class variables 
               Precondition: none
               Postcondition: defines private variables */
    bool IsEmpty();
          /*   Function: Determines whether the stack is empty
               Precondition: Stack has been initialized
               Postcondition: Function value = (stack is empty) */
    bool IsFull();
          /*   Function: Determines whether the stack is full
               Precondition: Stack has been initialized
               Postcondition: Function value = (stack is full) */
    int Size();
          /*   Function: Return the current size of the stack
               Precondition: Stack has been initialized
               Postcondition: If (stack is full) exception FullStack is thrown
                                   else newItem is at the top of the stack */
    void MakeEmpty();
          /*   Function: Empties the stack
               Precondition: Stack has been initialized
               Postcondition: Stack is empty */
    void Push(ItemType newItem);
          /*   Function: Adds newItem to the top of the stack
               Precondition: Stack has been initialized
               Postcondition: If (stack is full) exception FullStack is thrown
                                   else newItem is at the top of the stack */
    ItemType Pop();
          /*   Function: Returns & then removes top item from the stack
               Precondition: Stack has been initialized
               Postcondition: If (stack is empty) exception EmptyStack is thrown
                                   else top element has been removed from the stack */
    ItemType Top();
          /*   Function: Returns the top item from the stack
               Precondition: Stack has been initialized
               Postcondition: If (stack is empty) exception EmptyStack is thrown
                                   else top element has been removed from the stack */
    ~StackListType();
          /*   Function: destructor deallocates class variables 
               Precondition: none
               Postcondition: deallocates private variables */

private:
    struct NodeType
    {
          ItemType currentItem;  // Variable which hold all the incoming currentItem
          NodeType* next; // Creates a pointer that points to the next node in the list.
    };
    int size;          // Indicates the size of the stack	
    ItemType junk;
    NodeType* headPtr; // Creates a head pointer that will point to the begining of the list.
};

//=========================  Implementation  ================================//

template<class ItemType>
StackListType<ItemType>::StackListType()
{
    size = 0;
    headPtr = NULL;
}//     End of StackListType

template<class ItemType>
bool StackListType<ItemType>::IsEmpty()
{
    return (headPtr == NULL);
}//     End of IsEmpty

template<class ItemType>
bool StackListType<ItemType>::IsFull()
{    
    try
    {
        NodeType* tempPtr = new NodeType;
        delete tempPtr;
        return false;
    }
    catch(std::bad_alloc&)
    {
        return true;
    }
}//     End of IsFull

template<class ItemType>
int StackListType<ItemType>::Size()
{
    if(IsEmpty())
    {
        std::cout<<"nSTACK EMPTYn";
    }
    return size;
}//     End of Size

template<class ItemType>
void StackListType<ItemType>::MakeEmpty()
{
    size = 0;    
	
    if (!IsEmpty())
	{
        std::cout << "Destroying nodes ...n";

		while (!IsEmpty())
		{
			NodeType* tempPtr = headPtr;
			//std::cout << tempPtr-> currentItem << 'n';
			headPtr = headPtr-> next;
			delete tempPtr;
		}
	}     
}//     End of MakeEmpty

template<class ItemType>
void StackListType<ItemType>::Push(ItemType newItem)
{
    if(IsFull())
    {
        std::cout<<"nSTACK FULLn";
        return;
    }
    NodeType* tempPtr = new NodeType;
    tempPtr-> currentItem = newItem;
    tempPtr-> next = headPtr;
    headPtr = tempPtr;
    ++size;
}//     End of Push

template<class ItemType>
ItemType StackListType<ItemType>::Pop()
{
    if(IsEmpty())
    {
        std::cout<<"nSTACK EMPTYn";
        return junk;
    }
    else
    {  
        ItemType data = headPtr-> currentItem;  
        NodeType* tempPtr = headPtr;
        headPtr = headPtr-> next;
        delete tempPtr;
        --size;
        return data;
    }
}//     End of Pop

template<class ItemType>
ItemType StackListType<ItemType>::Top()
{
    if(IsEmpty())
    {
        std::cout<<"nSTACK EMPTYn";
        return junk;
    }
    else
    { 
        return headPtr-> currentItem;
    }
}//     End of Top

template<class ItemType>
StackListType<ItemType>::~StackListType()
{
    MakeEmpty();   
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
				
						// ============================================================================
//    Author: K Perkins
//    Date:   Apr 9, 2012
//    Taken From: http://programmingnotes.org/
//    File:  ClassStackListType.h
//    Description: This is a class which implements various functions
//          demonstrating the use of a stack. 
// ============================================================================
#include <iostream>         
 
template <class ItemType>
class StackListType
{
public:
    StackListType();
          /*   Function: constructor initializes class variables 
               Precondition: none
               Postcondition: defines private variables */
    bool IsEmpty();
          /*   Function: Determines whether the stack is empty
               Precondition: Stack has been initialized
               Postcondition: Function value = (stack is empty) */
    bool IsFull();
          /*   Function: Determines whether the stack is full
               Precondition: Stack has been initialized
               Postcondition: Function value = (stack is full) */
    int Size();
          /*   Function: Return the current size of the stack
               Precondition: Stack has been initialized
               Postcondition: If (stack is full) exception FullStack is thrown
                                   else newItem is at the top of the stack */
    void MakeEmpty();
          /*   Function: Empties the stack
               Precondition: Stack has been initialized
               Postcondition: Stack is empty */
    void Push(ItemType newItem);
          /*   Function: Adds newItem to the top of the stack
               Precondition: Stack has been initialized
               Postcondition: If (stack is full) exception FullStack is thrown
                                   else newItem is at the top of the stack */
    ItemType Pop();
          /*   Function: Returns & then removes top item from the stack
               Precondition: Stack has been initialized
               Postcondition: If (stack is empty) exception EmptyStack is thrown
                                   else top element has been removed from the stack */
    ItemType Top();
          /*   Function: Returns the top item from the stack
               Precondition: Stack has been initialized
               Postcondition: If (stack is empty) exception EmptyStack is thrown
                                   else top element has been removed from the stack */
    ~StackListType();
          /*   Function: destructor deallocates class variables 
               Precondition: none
               Postcondition: deallocates private variables */
 
private:
    struct NodeType
    {
          ItemType currentItem;  // Variable which hold all the incoming currentItem
          NodeType* next; // Creates a pointer that points to the next node in the list.
    };
    int size;          // Indicates the size of the stack	
    ItemType junk;
    NodeType* headPtr; // Creates a head pointer that will point to the begining of the list.
};
 
//=========================  Implementation  ================================//
 
template<class ItemType>
StackListType<ItemType>::StackListType()
{
    size = 0;
    headPtr = NULL;
}//     End of StackListType
 
template<class ItemType>
bool StackListType<ItemType>::IsEmpty()
{
    return (headPtr == NULL);
}//     End of IsEmpty
 
template<class ItemType>
bool StackListType<ItemType>::IsFull()
{    
    try
    {
        NodeType* tempPtr = new NodeType;
        delete tempPtr;
        return false;
    }
    catch(std::bad_alloc&)
    {
        return true;
    }
}//     End of IsFull
 
template<class ItemType>
int StackListType<ItemType>::Size()
{
    if(IsEmpty())
    {
        std::cout<<"nSTACK EMPTYn";
    }
    return size;
}//     End of Size
 
template<class ItemType>
void StackListType<ItemType>::MakeEmpty()
{
    size = 0;    
	
    if (!IsEmpty())
	{
        std::cout << "Destroying nodes ...n";
 
		while (!IsEmpty())
		{
			NodeType* tempPtr = headPtr;
			//std::cout << tempPtr-> currentItem << 'n';
			headPtr = headPtr-> next;
			delete tempPtr;
		}
	}     
}//     End of MakeEmpty
 
template<class ItemType>
void StackListType<ItemType>::Push(ItemType newItem)
{
    if(IsFull())
    {
        std::cout<<"nSTACK FULLn";
        return;
    }
    NodeType* tempPtr = new NodeType;
    tempPtr-> currentItem = newItem;
    tempPtr-> next = headPtr;
    headPtr = tempPtr;
    ++size;
}//     End of Push
 
template<class ItemType>
ItemType StackListType<ItemType>::Pop()
{
    if(IsEmpty())
    {
        std::cout<<"nSTACK EMPTYn";
        return junk;
    }
    else
    {  
        ItemType data = headPtr-> currentItem;  
        NodeType* tempPtr = headPtr;
        headPtr = headPtr-> next;
        delete tempPtr;
        --size;
        return data;
    }
}//     End of Pop
 
template<class ItemType>
ItemType StackListType<ItemType>::Top()
{
    if(IsEmpty())
    {
        std::cout<<"nSTACK EMPTYn";
        return junk;
    }
    else
    { 
        return headPtr-> currentItem;
    }
}//     End of Top
 
template<class ItemType>
StackListType<ItemType>::~StackListType()
{
    MakeEmpty();   
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

===== DEMONSTRATION HOW TO USE =====

Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.





		
		
			How To Use #include 'ClassStackListType.h'
			
C++
			
			#include <iostream>
#include "ClassStackListType.h"
using namespace std;

int  main()
{    // declare variables
     StackListType<char> charStack;
     StackListType<int> intStack;
     StackListType<float> floatStack;
     
     // ------ Char Example ------//
     char charArry[]="My Programming Notes Is Awesome";
     int counter=0;
     while(charArry[counter]!='\0')
     {
          charStack.Push(charArry[counter]);
          ++counter;
     }
     cout<<"charStack has "<<charStack.Size()<<" items in itn"
     <<"and contains the text ""<<charArry<<"" backwards:n";
     while(!charStack.IsEmpty())
     {
          cout<<charStack.Pop();
     }
     cout<<endl;     
     
     // ------ Int Example ------//
     int intArry[]={1,22,3,46,5,66,7,8,1987};
     counter=0;
     while(counter<9)
     {
          intStack.Push(intArry[counter]);
          ++counter;
     }
     cout<<"nintStack has "<<intStack.Size()<<" items in it.n"
     <<"The sum of the numbers in the stack is: ";
     counter=0;
     while(!intStack.IsEmpty())
     {
          counter+=intStack.Pop();
     }
     cout<<counter<<endl;
     
     // ------ Float Example ------//
     float floatArry[]={41.6,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,81.540};
     float sum=0;
     counter=0;
     while(counter<10)
     {
          floatStack.Push(floatArry[counter]);
          ++counter;
     }
     cout<<"nfloatStack has "<<floatStack.Size()<<" items in it.n"
     <<"The sum of the numbers in the stack is: ";
     while(!floatStack.IsEmpty())
     {
          sum+=floatStack.Pop();
     }
     cout<<sum<<endl;     
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
				
						#include <iostream>
#include "ClassStackListType.h"
using namespace std;
 
int  main()
{    // declare variables
     StackListType<char> charStack;
     StackListType<int> intStack;
     StackListType<float> floatStack;
     
     // ------ Char Example ------//
     char charArry[]="My Programming Notes Is Awesome";
     int counter=0;
     while(charArry[counter]!='\0')
     {
          charStack.Push(charArry[counter]);
          ++counter;
     }
     cout<<"charStack has "<<charStack.Size()<<" items in itn"
     <<"and contains the text ""<<charArry<<"" backwards:n";
     while(!charStack.IsEmpty())
     {
          cout<<charStack.Pop();
     }
     cout<<endl;     
     
     // ------ Int Example ------//
     int intArry[]={1,22,3,46,5,66,7,8,1987};
     counter=0;
     while(counter<9)
     {
          intStack.Push(intArry[counter]);
          ++counter;
     }
     cout<<"nintStack has "<<intStack.Size()<<" items in it.n"
     <<"The sum of the numbers in the stack is: ";
     counter=0;
     while(!intStack.IsEmpty())
     {
          counter+=intStack.Pop();
     }
     cout<<counter<<endl;
     
     // ------ Float Example ------//
     float floatArry[]={41.6,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,81.540};
     float sum=0;
     counter=0;
     while(counter<10)
     {
          floatStack.Push(floatArry[counter]);
          ++counter;
     }
     cout<<"nfloatStack has "<<floatStack.Size()<<" items in it.n"
     <<"The sum of the numbers in the stack is: ";
     while(!floatStack.IsEmpty())
     {
          sum+=floatStack.Pop();
     }
     cout<<sum<<endl;     
}// http://programmingnotes.org/

Once compiled, you should get this as your output

charStack has 31 items in it and contains the text "My Programming Notes Is Awesome" backwards: emosewA sI setoN gnimmargorP yM
intStack has 9 items in it. The sum of the numbers in the stack is: 2145
floatStack has 10 items in it. The sum of the numbers in the stack is: 286.717

C++ || Stack Based Postfix Evaluation (Single Digit)

March 24, 2012 admin No comments

This page consists of another homework assignment which was presented in a C++ Data Structures course. While the previously discussed program dealt with converting Infix expressions to Postfix, this program will demonstrate exactly how to evaluate them.

NOTE: Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!

REQUIRED KNOWLEDGE FOR THIS PROGRAM

What Is Postfix? How To Convert Infix To Postfix Equations Stack Data Structure Cin.getline How To Evaluate Postfix Expressions The Order Of Operations #include "ClassStackType.h"

The title of this page is called – “Stack Based Postfix Evaluation (Single Digit).” Why “single digit?” The program demonstrated on this page has the ability to evaluate a postfix equation, but it only has the ability to evaluate single digit values. What do I mean by that? Consider the infix equation: 5+2. When that expression is converted to postfix, it will come out to be: 52+, and the answer will be 7 (5+2=7). But what if we have an equation like 12+2? When that expression is converted to postfix, it will come out to be: 122+. The postfix conversion is correct, but when you try to evaluate the expression, we do not know if the math operation should be 12+2 or 1+22, it can be read either way.

Question: So why is this program being displayed if it only works for single digits?
Answer: Because it demonstrates the process of evaluating postfix equations very well.

Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!

Before we get into things, here is a helpful algorithm for evaluating a postfix expression in pseudo code:





		
		
			// An algorithm for postfix evaluation.
// For example,  (1 + 2) / (5 + 6) translates to  1 2 + 5 6 + /
// which equals the result of 0.272727
// Valid operands are single digits: 0-9
// Valid operators are: +, -, *, /, ^, $
// Highest precedence: ^, $
// Lowest precedence: +,-
// the operators ')' and '('never goes on stack.

double EvaluatePostfix(string postfix)
{
  while there is input
  {
    if input is a number
        push current number on stack
    else if input is a math operator and stack is not empty
        set operand2 to the top of the operand stack
            pop the stack
        set operand1 to the top of the operand stack
            pop the stack
        apply the math operation that represents to operand1 and operand2
            push the result onto the stack
    else error
  }
  // When the loop is finished, the operand stack will contain one item,
  // the result of evaluating the expression
  pop the stack
  return the answer to the caller
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
				
						// An algorithm for postfix evaluation.
// For example,  (1 + 2) / (5 + 6) translates to  1 2 + 5 6 + /
// which equals the result of 0.272727
// Valid operands are single digits: 0-9
// Valid operators are: +, -, *, /, ^, $
// Highest precedence: ^, $
// Lowest precedence: +,-
// the operators ')' and '('never goes on stack.
 
double EvaluatePostfix(string postfix)
{
  while there is input
  {
    if input is a number
        push current number on stack
    else if input is a math operator and stack is not empty
        set operand2 to the top of the operand stack
            pop the stack
        set operand1 to the top of the operand stack
            pop the stack
        apply the math operation that represents to operand1 and operand2
            push the result onto the stack
    else error
  }
  // When the loop is finished, the operand stack will contain one item,
  // the result of evaluating the expression
  pop the stack
  return the answer to the caller
}// http://programmingnotes.org/

Once you understand the process of converting from infix to postfix, adding the ability to evaluate multiple digits within this program should be doable.

======= POSTFIX EVALUATION =======

This program uses a custom template.h class. To obtain the code for that class, click here.





		
		
			Postfix Evaluation (Single Digit)
			
C++
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 24, 2012
//    Taken From: http://programmingnotes.org/
//    File:  PostfixEvaluation.cpp
//    Description: Demonstrate the use of a stack based postfix evaluation.
// ============================================================================
#include <iostream>
#include <cstdlib>
#include <cmath>
#include "ClassStackType.h"
using namespace std;

// function prototypes
void DisplayDirections();
double EvaluatePostfix(char* postfix);
bool IsMathOperator(char token);
double DoMath(double op1, double op2, char token);

int main()
{
     // declare variables
     char expression[50]; // array holding the postfix data
     double answer = 0;

     // display directions to user
     DisplayDirections();

     // get data from user
     cout<<"\nPlease enter a postfix expression: ";
     cin.getline(expression, sizeof(expression));

     cout <<"\nThe postfix expression = "<<expression<<endl;

     cout<<"\nCalculations:\n";

     answer = EvaluatePostfix(expression);

     cout<<"\nFinal answer = "<<answer<<endl;

     return 0;
}// end of main

void DisplayDirections()
{
     cout << "\n==== Postfix Evaluation ====\n"
         <<"\nMath Operators:\n"
         <<"+ || Addition\n"
         <<"- || Subtraction\n"
         <<"* || Multiplication\n"
         <<"/ || Division\n"
         <<"% || Modulus\n"
         <<"^ || Power\n"
         <<"$ || Square Rootn\n"
         <<"Sample Postfix Equation: 45^14*232+$2-/12%24*/* \n";
}// end of DisplayDirections

double EvaluatePostfix(char* postfix)
{
    // declare function variables
    int counter = 0;
    int currentNum = 0;
    char token = 'a';
    double op1 = 0;
    double op2 = 0;
    double answer = 0;
    StackType<double> doubleStack;

    // loop thru array until there is no more data
    while(postfix[counter] != '\0')
    {
        // push numbers onto the stack
        if(isdigit(postfix[counter]))
        {
            currentNum = postfix[counter] - '0';
            doubleStack.Push(currentNum);
        }
        else if(isspace(postfix[counter]))
        {
            // DO NOTHING
        }
        // if expression is a math operator, pop numbers from stack
        // & send the popped numbers to the 'DoMath' function
        else if((IsMathOperator(postfix[counter])) && (!doubleStack.IsEmpty()))
        {
            token = postfix[counter];

            // if expression is square root operation
            // only pop stack once
            if(token == '$')
            {
                op2 = 0;
                op1 = doubleStack.Top();
                doubleStack.Pop();

                answer = DoMath(op1,op2,token);
                doubleStack.Push(answer);
            }
            else
            {
                op2 = doubleStack.Top();
                doubleStack.Pop();
                op1 = doubleStack.Top();
                doubleStack.Pop();

                answer = DoMath(op1,op2,token);
                doubleStack.Push(answer);
            }
        }
        else
        {
            cout<<"\nINVALID INPUT\n";
            exit(1);
        }
        ++counter;
    }
    // pop the final answer from the stack, and return to main
    answer = doubleStack.Top();
    doubleStack.Pop();

    return answer;
}// end of EvaluatePostfix

bool IsMathOperator(char token)
{// this function checks if operand is a math operator
     switch(token)
     {
        case '+':
            return true;
            break;
        case '-':
            return true;
            break;
        case '*':
            return true;
            break;
        case '/':
            return true;
            break;
        case '%':
            return true;
            break;
        case '^':
            return true;
            break;
        case '$':
            return true;
            break;
        default:
            return false;
            break;
     }
}// end of IsMathOperator

double DoMath(double op1, double op2, char token)
{// this function carries out the actual math process
    double ans = 0;
    switch(token)
    {
        case '+':
            cout<<op1<<token<<op2<<" = ";
            ans = op1 + op2;
            break;
        case '-':
            cout<<op1<<token<<op2<<" = ";
            ans = op1 - op2;
            break;
        case '*':
            cout<<op1<<token<<op2<<" = ";
            ans = op1 * op2;
            break;
        case '/':
            cout<<op1<<token<<op2<<" = ";
            ans = op1 / op2;
            break;
        case '%':
            cout<<op1<<token<<op2<<" = ";
            ans = (int)op1 % (int)op2;
            break;
        case '^':
            cout<<op1<<token<<op2<<" = ";
            ans = pow(op1, op2);
            break;
        case '$':
            cout<<char(251)<<op1<<" = ";
            ans = sqrt(op1);
            break;
        default:
            ans = 0;
            break;
    }
    cout<<ans<<endl;
    return ans;
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 24, 2012
//    Taken From: http://programmingnotes.org/
//    File:  PostfixEvaluation.cpp
//    Description: Demonstrate the use of a stack based postfix evaluation.
// ============================================================================
#include <iostream>
#include <cstdlib>
#include <cmath>
#include "ClassStackType.h"
using namespace std;
 
// function prototypes
void DisplayDirections();
double EvaluatePostfix(char* postfix);
bool IsMathOperator(char token);
double DoMath(double op1, double op2, char token);
 
int main()
{
     // declare variables
     char expression[50]; // array holding the postfix data
     double answer = 0;
 
     // display directions to user
     DisplayDirections();
 
     // get data from user
     cout<<"\nPlease enter a postfix expression: ";
     cin.getline(expression, sizeof(expression));
 
     cout <<"\nThe postfix expression = "<<expression<<endl;
 
     cout<<"\nCalculations:\n";
 
     answer = EvaluatePostfix(expression);
 
     cout<<"\nFinal answer = "<<answer<<endl;
 
     return 0;
}// end of main
 
void DisplayDirections()
{
     cout << "\n==== Postfix Evaluation ====\n"
         <<"\nMath Operators:\n"
         <<"+ || Addition\n"
         <<"- || Subtraction\n"
         <<"* || Multiplication\n"
         <<"/ || Division\n"
         <<"% || Modulus\n"
         <<"^ || Power\n"
         <<"$ || Square Rootn\n"
         <<"Sample Postfix Equation: 45^14*232+$2-/12%24*/* \n";
}// end of DisplayDirections
 
double EvaluatePostfix(char* postfix)
{
    // declare function variables
    int counter = 0;
    int currentNum = 0;
    char token = 'a';
    double op1 = 0;
    double op2 = 0;
    double answer = 0;
    StackType<double> doubleStack;
 
    // loop thru array until there is no more data
    while(postfix[counter] != '\0')
    {
        // push numbers onto the stack
        if(isdigit(postfix[counter]))
        {
            currentNum = postfix[counter] - '0';
            doubleStack.Push(currentNum);
        }
        else if(isspace(postfix[counter]))
        {
            // DO NOTHING
        }
        // if expression is a math operator, pop numbers from stack
        // & send the popped numbers to the 'DoMath' function
        else if((IsMathOperator(postfix[counter])) && (!doubleStack.IsEmpty()))
        {
            token = postfix[counter];
 
            // if expression is square root operation
            // only pop stack once
            if(token == '$')
            {
                op2 = 0;
                op1 = doubleStack.Top();
                doubleStack.Pop();
 
                answer = DoMath(op1,op2,token);
                doubleStack.Push(answer);
            }
            else
            {
                op2 = doubleStack.Top();
                doubleStack.Pop();
                op1 = doubleStack.Top();
                doubleStack.Pop();
 
                answer = DoMath(op1,op2,token);
                doubleStack.Push(answer);
            }
        }
        else
        {
            cout<<"\nINVALID INPUT\n";
            exit(1);
        }
        ++counter;
    }
    // pop the final answer from the stack, and return to main
    answer = doubleStack.Top();
    doubleStack.Pop();
 
    return answer;
}// end of EvaluatePostfix
 
bool IsMathOperator(char token)
{// this function checks if operand is a math operator
     switch(token)
     {
        case '+':
            return true;
            break;
        case '-':
            return true;
            break;
        case '*':
            return true;
            break;
        case '/':
            return true;
            break;
        case '%':
            return true;
            break;
        case '^':
            return true;
            break;
        case '$':
            return true;
            break;
        default:
            return false;
            break;
     }
}// end of IsMathOperator
 
double DoMath(double op1, double op2, char token)
{// this function carries out the actual math process
    double ans = 0;
    switch(token)
    {
        case '+':
            cout<<op1<<token<<op2<<" = ";
            ans = op1 + op2;
            break;
        case '-':
            cout<<op1<<token<<op2<<" = ";
            ans = op1 - op2;
            break;
        case '*':
            cout<<op1<<token<<op2<<" = ";
            ans = op1 * op2;
            break;
        case '/':
            cout<<op1<<token<<op2<<" = ";
            ans = op1 / op2;
            break;
        case '%':
            cout<<op1<<token<<op2<<" = ";
            ans = (int)op1 % (int)op2;
            break;
        case '^':
            cout<<op1<<token<<op2<<" = ";
            ans = pow(op1, op2);
            break;
        case '$':
            cout<<char(251)<<op1<<" = ";
            ans = sqrt(op1);
            break;
        default:
            ans = 0;
            break;
    }
    cout<<ans<<endl;
    return ans;
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output
(Note: the code was compile three separate times to display different output)

====== RUN 1 ======
==== Postfix Evaluation ==== Math Operators: + || Addition - || Subtraction * || Multiplication / || Division % || Modulus ^ || Power $ || Square Root Sample Postfix Equation: 45^14*232+$2-/12%24*/* Please enter a postfix expression: 1 2 + 5 6 + / The postfix expression = 1 2 + 5 6 + / Calculations: 1+2 = 3 5+6 = 11 3/11 = 0.272727 Final answer = 0.272727 ====== RUN 2 ====== ==== Postfix Evaluation ==== Math Operators: + || Addition - || Subtraction * || Multiplication / || Division % || Modulus ^ || Power $ || Square Root Sample Postfix Equation: 45^14*232+$2-/12%24*/* Please enter a postfix expression: 35*76^+ The postfix expression = 35*76^+ Calculations: 3*5 = 15 7^6 = 117649 15+117649 = 117664 Final answer = 117664 ====== RUN 3 ====== ==== Postfix Evaluation ==== Math Operators: + || Addition - || Subtraction * || Multiplication / || Division % || Modulus ^ || Power $ || Square Root Sample Postfix Equation: 45^14*232+$2-/12%24*/* Please enter a postfix expression: 45^4*32+$2-/12%24*/* The postfix expression = 45^4*32+$2-/12%24*/*
Calculations: 4^5 = 1024 1024*4 = 4096 3+2 = 5 √5 = 2.23607 2.23607-2 = 0.236068 4096/0.236068 = 17350.9 1%2 = 1 2*4 = 8 1/8 = 0.125 17350.9*0.125 = 2168.87 Final answer = 2168.87

C++ || Snippet – Array Based Custom Template Stack Sample Code

March 22, 2012 admin No comments

This page will consist of sample code for a custom array based template stack.

REQUIRED KNOWLEDGE FOR THIS SNIPPET

Classes Template Classes - What Are They? Stacks LIFO - What Is It? #include < stack>





		
		
			#include 'ClassStackType.h'
			
C++
			
			// ============================================================================
//    Author: K Perkins
//    Date:   Mar 22, 2012
//    Taken From: http://programmingnotes.org/
//    File:  ClassStackType.h
//    Description: This is a class which implements various functions
//          demonstrating the use of a stack. 
// ============================================================================
#include <iostream>

template <class ItemType>
class StackType
{
public:
	StackType();
		/*   Function: constructor initializes class variables 
			Precondition: none
			Postcondition: defines private variables */
	bool IsEmpty();
		/*   Function: Determines whether the stack is empty
			Precondition: Stack has been initialized
			Postcondition: Function value = (stack is empty) */
	bool IsFull();
		/*   Function: Determines whether the stack is full
			Precondition: Stack has been initialized
			Postcondition: Function value = (stack is full) */
	int Size();
		/*   Function: Return the current size of the stack
			Precondition: Stack has been initialized
			Postcondition: If (stack is full) exception FullStack is thrown
							else newItem is at the top of the stack */	
	void MakeEmpty();
		/*   Function: Empties the stack
			Precondition: Stack has been initialized
			Postcondition: Stack is empty */
	void Push(ItemType newItem);
		/*   Function: Adds newItem to the top of the stack
			Precondition: Stack has been initialized
			Postcondition: If (stack is full) exception FullStack is thrown
							else newItem is at the top of the stack */
	ItemType Pop();
		/*   Function: Returns & then removes top item from the stack
			Precondition: Stack has been initialized
			Postcondition: If (stack is empty) exception EmptyStack is thrown
							else top element has been removed from the stack */
	ItemType Top();
		/*   Function: Returns the top item from the stack
			Precondition: Stack has been initialized
			Postcondition: If (stack is empty) exception EmptyStack is thrown
							else top element has been removed from the stack */
	~StackType();
		/*   Function: destructor deallocates class variables 
			Precondition: none
			Postcondition: deallocates private variables */

private:
	int top;		// indicates which element is on top
	int MAX_ITEMS;     // max number of items in the list
	ItemType stack[200];	// array holding the popped/pushed data
};

//=========================  Implementation  ================================//

template<class ItemType>
StackType<ItemType>::StackType()
{
	top = -1;
	MAX_ITEMS = 200;
}//	End of StackType

template<class ItemType>
bool StackType<ItemType>::IsEmpty()
{
	return (top == -1);
}//	End of IsEmpty

template<class ItemType>
bool StackType<ItemType>::IsFull()
{
	return (top==(MAX_ITEMS-1));
}//	End of IsFull

template<class ItemType>
int StackType<ItemType>::Size()
{
	if(IsEmpty())
	{
		std::cout<<"nSTACK EMPTYn";
		return('?');
	}
	return top+1;
}//	End of Size

template<class ItemType>
void StackType<ItemType>::MakeEmpty()
{
	top = -1;
}//	End of MakeEmpty

template<class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
	if(IsFull())
	{
		std::cout<<"nSTACK FULLn";
		return;
	}
	stack[++top]=newItem;
}//	End of Push

template<class ItemType>
ItemType StackType<ItemType>::Pop()
{
	if(IsEmpty())
	{
		std::cout<<"nSTACK EMPTYn";
		return('?');
	}	
	return(stack[top--]);
}//	End of Pop

template<class ItemType>
ItemType StackType<ItemType>::Top()
{
	if(IsEmpty())
	{
		std::cout<<"nSTACK EMPTYn";
		return('?');
	}
	return(stack[top]);
}//	End of Top

template<class ItemType>
StackType<ItemType>::~StackType()
{
	top = -1;
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
				
						// ============================================================================
//    Author: K Perkins
//    Date:   Mar 22, 2012
//    Taken From: http://programmingnotes.org/
//    File:  ClassStackType.h
//    Description: This is a class which implements various functions
//          demonstrating the use of a stack. 
// ============================================================================
#include <iostream>
 
template <class ItemType>
class StackType
{
public:
	StackType();
		/*   Function: constructor initializes class variables 
			Precondition: none
			Postcondition: defines private variables */
	bool IsEmpty();
		/*   Function: Determines whether the stack is empty
			Precondition: Stack has been initialized
			Postcondition: Function value = (stack is empty) */
	bool IsFull();
		/*   Function: Determines whether the stack is full
			Precondition: Stack has been initialized
			Postcondition: Function value = (stack is full) */
	int Size();
		/*   Function: Return the current size of the stack
			Precondition: Stack has been initialized
			Postcondition: If (stack is full) exception FullStack is thrown
							else newItem is at the top of the stack */	
	void MakeEmpty();
		/*   Function: Empties the stack
			Precondition: Stack has been initialized
			Postcondition: Stack is empty */
	void Push(ItemType newItem);
		/*   Function: Adds newItem to the top of the stack
			Precondition: Stack has been initialized
			Postcondition: If (stack is full) exception FullStack is thrown
							else newItem is at the top of the stack */
	ItemType Pop();
		/*   Function: Returns & then removes top item from the stack
			Precondition: Stack has been initialized
			Postcondition: If (stack is empty) exception EmptyStack is thrown
							else top element has been removed from the stack */
	ItemType Top();
		/*   Function: Returns the top item from the stack
			Precondition: Stack has been initialized
			Postcondition: If (stack is empty) exception EmptyStack is thrown
							else top element has been removed from the stack */
	~StackType();
		/*   Function: destructor deallocates class variables 
			Precondition: none
			Postcondition: deallocates private variables */
 
private:
	int top;		// indicates which element is on top
	int MAX_ITEMS;     // max number of items in the list
	ItemType stack[200];	// array holding the popped/pushed data
};
 
//=========================  Implementation  ================================//
 
template<class ItemType>
StackType<ItemType>::StackType()
{
	top = -1;
	MAX_ITEMS = 200;
}//	End of StackType
 
template<class ItemType>
bool StackType<ItemType>::IsEmpty()
{
	return (top == -1);
}//	End of IsEmpty
 
template<class ItemType>
bool StackType<ItemType>::IsFull()
{
	return (top==(MAX_ITEMS-1));
}//	End of IsFull
 
template<class ItemType>
int StackType<ItemType>::Size()
{
	if(IsEmpty())
	{
		std::cout<<"nSTACK EMPTYn";
		return('?');
	}
	return top+1;
}//	End of Size
 
template<class ItemType>
void StackType<ItemType>::MakeEmpty()
{
	top = -1;
}//	End of MakeEmpty
 
template<class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
	if(IsFull())
	{
		std::cout<<"nSTACK FULLn";
		return;
	}
	stack[++top]=newItem;
}//	End of Push
 
template<class ItemType>
ItemType StackType<ItemType>::Pop()
{
	if(IsEmpty())
	{
		std::cout<<"nSTACK EMPTYn";
		return('?');
	}	
	return(stack[top--]);
}//	End of Pop
 
template<class ItemType>
ItemType StackType<ItemType>::Top()
{
	if(IsEmpty())
	{
		std::cout<<"nSTACK EMPTYn";
		return('?');
	}
	return(stack[top]);
}//	End of Top
 
template<class ItemType>
StackType<ItemType>::~StackType()
{
	top = -1;
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

===== DEMONSTRATION HOW TO USE =====

Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.





		
		
			How To Use #include 'ClassStackType.h'
			
C++
			
			#include <iostream>
#include "ClassStackType.h"
using namespace std;

int  main()
{    // declare variables
	StackType<char> charStack;
	StackType<int> intStack;
	StackType<float> floatStack;
	
	// ------ Char Example ------//
	char charArry[]="My Programming Notes";
	int counter=0;
	while(charArry[counter]!='�')
	{
		charStack.Push(charArry[counter]);
		++counter;
	}
	cout<<"charStack has "<<charStack.Size()<<" items in itn"
	<<"and contains the text: "<<charArry<<" backwards ";
	while(!charStack.IsEmpty())
	{
		cout<<charStack.Pop();
	}
	cout<<endl;	
	
	// ------ Int Example ------//
	int intArry[]={1,2,3,4,5,6,7,8,9};
	counter=0;
	while(counter<9)
	{
		intStack.Push(intArry[counter]);
		++counter;
	}
	cout<<"intStack has "<<intStack.Size()<<" items in it.n"
	<<"The sum of the numbers in the stack is: ";
	counter=0;
	while(!intStack.IsEmpty())
	{
		counter+=intStack.Pop();
	}
	cout<<counter<<endl;
	
	// ------ Float Example ------//
	float floatArry[]={1.6,2.8,3.9,4.4,5.987,6.23,7.787,8.99,9.6,1.540};
	float sum=0;
	counter=0;
	while(counter<10)
	{
		floatStack.Push(floatArry[counter]);
		++counter;
	}
	cout<<"floatStack has "<<floatStack.Size()<<" items in it.n"
	<<"The sum of the numbers in the stack is: ";
	while(!floatStack.IsEmpty())
	{
		sum+=floatStack.Pop();
	}
	cout<<sum<<endl;	
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
				
						#include <iostream>
#include "ClassStackType.h"
using namespace std;
 
int  main()
{    // declare variables
	StackType<char> charStack;
	StackType<int> intStack;
	StackType<float> floatStack;
	
	// ------ Char Example ------//
	char charArry[]="My Programming Notes";
	int counter=0;
	while(charArry[counter]!='')
	{
		charStack.Push(charArry[counter]);
		++counter;
	}
	cout<<"charStack has "<<charStack.Size()<<" items in itn"
	<<"and contains the text: "<<charArry<<" backwards ";
	while(!charStack.IsEmpty())
	{
		cout<<charStack.Pop();
	}
	cout<<endl;	
	
	// ------ Int Example ------//
	int intArry[]={1,2,3,4,5,6,7,8,9};
	counter=0;
	while(counter<9)
	{
		intStack.Push(intArry[counter]);
		++counter;
	}
	cout<<"intStack has "<<intStack.Size()<<" items in it.n"
	<<"The sum of the numbers in the stack is: ";
	counter=0;
	while(!intStack.IsEmpty())
	{
		counter+=intStack.Pop();
	}
	cout<<counter<<endl;
	
	// ------ Float Example ------//
	float floatArry[]={1.6,2.8,3.9,4.4,5.987,6.23,7.787,8.99,9.6,1.540};
	float sum=0;
	counter=0;
	while(counter<10)
	{
		floatStack.Push(floatArry[counter]);
		++counter;
	}
	cout<<"floatStack has "<<floatStack.Size()<<" items in it.n"
	<<"The sum of the numbers in the stack is: ";
	while(!floatStack.IsEmpty())
	{
		sum+=floatStack.Pop();
	}
	cout<<sum<<endl;	
}// http://programmingnotes.org/

Once compiled, you should get this as your output

charStack has 20 items in it and contains the text: My Programming Notes backwards setoN gnimmargorP yM
intStack has 9 items in it. The sum of the numbers in the stack is: 45
floatStack has 10 items in it. The sum of the numbers in the stack is: 52.834

C++ || 8 Different Ways To Reverse A String/Character Array In C++

March 01, 2012 admin 2 Comments

This page will consist of 8 different ways to reverse a character array, and a string literal (std::string).

REQUIRED KNOWLEDGE FOR THE PROGRAMS

Character Arrays String Literals Cin.getline - Use For Char Arrays Getline - Use For std::string Length Strlen Strcpy While Loops For Loops Recursion - What is it? #include < algorithm> #include < stack>

The methods on this page will be broken up into sections. This page will list:

(3) methods which reverses string literals (std::string) (4) methods which reverses character arrays (1) method which utilizes the stack to "reverse" a character sequence

Some methods listed on this page demonstrates the use of reversing a character sequence without the use of strlen/length.

======= REVERSE AN STD::STRING =======





		
		
			#1 - Reverse String Using STL Function
			
C++
			
			#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
	// declare variable
	string name="";

	cout << "Enter your name: ";
	getline(cin,name);

	// built in C++ function to reverse an std::string
	reverse(name.begin(), name.end());
	
	cout <<"\nYour name reversed is: " <<name << endl;

	return 0;
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
				
						#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int main()
{
	// declare variable
	string name="";
 
	cout << "Enter your name: ";
	getline(cin,name);
 
	// built in C++ function to reverse an std::string
	reverse(name.begin(), name.end());
	
	cout <<"\nYour name reversed is: " <<name << endl;
 
	return 0;
}// http://programmingnotes.org/

SAMPLE OUTPUT

Enter your name: My Programming Notes
Your name reversed is: setoN gnimmargorP yM





		
		
			#2 - Reverse String Recursive Method, No Length()
			
C++
			
			#include <iostream>
#include <string>
using namespace std;

// function prototypes
void Reverse(string name);

int main()
{
	// declare variable
	string name="";

	// get user data
	cout<<"Enter your name: ";
	getline(cin,name);

	cout<<"\nYour name reversed is: ";

	// function declaration
	Reverse(name);
	cout<<endl;

	return 0;
}// end of main

void Reverse(string name)
{
	if(name == "") // the base case
	{
		return;
	}
	else // the recursive step
	{
		Reverse(name.substr(1));			
		cout<<name.at(0);
	}
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
				
						#include <iostream>
#include <string>
using namespace std;
 
// function prototypes
void Reverse(string name);
 
int main()
{
	// declare variable
	string name="";
 
	// get user data
	cout<<"Enter your name: ";
	getline(cin,name);
 
	cout<<"\nYour name reversed is: ";
 
	// function declaration
	Reverse(name);
	cout<<endl;
 
	return 0;
}// end of main
 
void Reverse(string name)
{
	if(name == "") // the base case
	{
		return;
	}
	else // the recursive step
	{
		Reverse(name.substr(1));			
		cout<<name.at(0);
	}
}// http://programmingnotes.org/

SAMPLE OUTPUT

Enter your name: My Programming Notes
Your name reversed is: setoN gnimmargorP yM





		
		
			#3 - Reverse String Iterative Method, Using Length()
			
C++
			
			#include <iostream>
#include <string>
using namespace std;

// function prototypes
void Reverse(string name);

int main()
{
	// declare variable
	string name="";

	// get user data
	cout<<"Enter your name: ";
	getline(cin,name);

	cout<<"\nYour name reversed is: ";

	// function declaration
	Reverse(name);
	cout<<endl;

	return 0;
}// end of main

void Reverse(string name)
{
	// get the length of the string
	int nameLength = name.length()-1;

	while(nameLength >= 0)
	{
		cout<<name[nameLength];
		--nameLength;
	}
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
				
						#include <iostream>
#include <string>
using namespace std;
 
// function prototypes
void Reverse(string name);
 
int main()
{
	// declare variable
	string name="";
 
	// get user data
	cout<<"Enter your name: ";
	getline(cin,name);
 
	cout<<"\nYour name reversed is: ";
 
	// function declaration
	Reverse(name);
	cout<<endl;
 
	return 0;
}// end of main
 
void Reverse(string name)
{
	// get the length of the string
	int nameLength = name.length()-1;
 
	while(nameLength >= 0)
	{
		cout<<name[nameLength];
		--nameLength;
	}
}// http://programmingnotes.org/

SAMPLE OUTPUT

Enter your name: My Programming Notes
Your name reversed is: setoN gnimmargorP yM

======= REVERSE A CHARACTER ARRAY =======

The following will demonstrate (4) methods which reverses a character array.





		
		
			#4 - Reverse Char Array Recursive Method, No Strlen
			
C++
			
			#include <iostream>
using namespace std;

// function prototype
void Reverse(char name[]);

int main()
{
	// declare variable
	char name[30];

	// get user data
	cout<<"Enter your name: ";
	cin.getline(name, sizeof(name));

	cout<<"\nYour name reversed is: ";

	// function declaration
	Reverse(name);
	cout<<endl;

	return 0;
}// end of main

void Reverse(char name[])
{
	if(*name=='\0') // the base case
	{
		return;
	}
	else // the recursive step
	{
		Reverse(name+1);
		cout<<*(name);
	}
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
				
						#include <iostream>
using namespace std;
 
// function prototype
void Reverse(char name[]);
 
int main()
{
	// declare variable
	char name[30];
 
	// get user data
	cout<<"Enter your name: ";
	cin.getline(name, sizeof(name));
 
	cout<<"\nYour name reversed is: ";
 
	// function declaration
	Reverse(name);
	cout<<endl;
 
	return 0;
}// end of main
 
void Reverse(char name[])
{
	if(*name=='\0') // the base case
	{
		return;
	}
	else // the recursive step
	{
		Reverse(name+1);
		cout<<*(name);
	}
}// http://programmingnotes.org/

SAMPLE OUTPUT

Enter your name: My Programming Notes
Your name reversed is: setoN gnimmargorP yM





		
		
			#5 - Reverse Char Array Iterative Method, No Strlen
			
C++
			
			#include <iostream>
using namespace std;

// function prototypes
void Reverse(char name[]);

int main()
{
	// declare variable
	char name[30];

	// get user data
	cout<<"Enter your name: ";
	cin.getline(name, sizeof(name));

	cout<<"\nYour name reversed is: ";

	// function declaration
	Reverse(name);
	cout<<endl;

	return 0;
}// end of main

void Reverse(char name[])
{
	int nameLength = 0;

	//get the length of array
	while(name[nameLength] != '\0')
	{
		++nameLength;
	}

	//decrease the length of by 1
	--nameLength;

	// display reversed string
	while(nameLength >= 0)
	{
		cout<<name[nameLength];
		--nameLength;
	}
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
				
						#include <iostream>
using namespace std;
 
// function prototypes
void Reverse(char name[]);
 
int main()
{
	// declare variable
	char name[30];
 
	// get user data
	cout<<"Enter your name: ";
	cin.getline(name, sizeof(name));
 
	cout<<"\nYour name reversed is: ";
 
	// function declaration
	Reverse(name);
	cout<<endl;
 
	return 0;
}// end of main
 
void Reverse(char name[])
{
	int nameLength = 0;
 
	//get the length of array
	while(name[nameLength] != '\0')
	{
		++nameLength;
	}
 
	//decrease the length of by 1
	--nameLength;
 
	// display reversed string
	while(nameLength >= 0)
	{
		cout<<name[nameLength];
		--nameLength;
	}
}// http://programmingnotes.org/

SAMPLE OUTPUT

Enter your name: My Programming Notes
Your name reversed is: setoN gnimmargorP yM





		
		
			#6 - Reverse Char Array Iterative Method, No Strlen
			
C++
			
			#include <iostream>
#include <cstring>
using namespace std;

// function prototypes
void Reverse(char name[]);

int main()
{
	// declare variable
	char name[30];

	// get user data
	cout<<"Enter your name: ";
	cin.getline(name, sizeof(name));

	// function declaration
	Reverse(name);

	cout<<"\nYour name reversed is: "<< name<<endl;

	return 0;
}// end of main

void Reverse(char name[])
{
	// private variables
	int nameLength = 0;
	char copy[30];

	strcpy(copy,name);

	//get lenght of array
	while(name[nameLength] != '\0')
	{
		++nameLength;
	}

	//decrease the length of by 1
	--nameLength;

	// reverse the array
	for(int x = 0; x <= nameLength; ++x)
	{
		// rearange the order of the two arrays
		name[nameLength - x] = copy[x];
	}	
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
				
						#include <iostream>
#include <cstring>
using namespace std;
 
// function prototypes
void Reverse(char name[]);
 
int main()
{
	// declare variable
	char name[30];
 
	// get user data
	cout<<"Enter your name: ";
	cin.getline(name, sizeof(name));
 
	// function declaration
	Reverse(name);
 
	cout<<"\nYour name reversed is: "<< name<<endl;
 
	return 0;
}// end of main
 
void Reverse(char name[])
{
	// private variables
	int nameLength = 0;
	char copy[30];
 
	strcpy(copy,name);
 
	//get lenght of array
	while(name[nameLength] != '\0')
	{
		++nameLength;
	}
 
	//decrease the length of by 1
	--nameLength;
 
	// reverse the array
	for(int x = 0; x <= nameLength; ++x)
	{
		// rearange the order of the two arrays
		name[nameLength - x] = copy[x];
	}	
}// http://programmingnotes.org/

SAMPLE OUTPUT

Enter your name: My Programming Notes
Your name reversed is: setoN gnimmargorP yM





		
		
			#7 - Reverse Char Array Iterative Method, Using Strlen
			
C++
			
			#include <iostream>
#include <cstring>
using namespace std;

// function prototypes
void Reverse(char name[]);

int main()
{
	// declare variable
	char name[30];

	// get user data
	cout<<"Enter your name: ";
	cin.getline(name, sizeof(name));

	// function declaration
	Reverse(name);

	cout<<"\nYour name reversed is: "<< name<<endl;

	return 0;
}// end of main

void Reverse(char name[])
{
	// get the length of the current word in the array index
	int nameLength = strlen(name)-1;
	
	// increment thru each letter within the current char array index
	// reversing the order of the array
	for(int currentChar=0; currentChar < nameLength; --nameLength, ++currentChar)
	{
		// copy 1st letter in the array index into temp
		char temp = name[currentChar]; 
		// copy last letter in the array index into the 1st array index
		name[currentChar] = name[nameLength];
		// copy temp into last array index
		name[nameLength] = temp;
	}
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
				
						#include <iostream>
#include <cstring>
using namespace std;
 
// function prototypes
void Reverse(char name[]);
 
int main()
{
	// declare variable
	char name[30];
 
	// get user data
	cout<<"Enter your name: ";
	cin.getline(name, sizeof(name));
 
	// function declaration
	Reverse(name);
 
	cout<<"\nYour name reversed is: "<< name<<endl;
 
	return 0;
}// end of main
 
void Reverse(char name[])
{
	// get the length of the current word in the array index
	int nameLength = strlen(name)-1;
	
	// increment thru each letter within the current char array index
	// reversing the order of the array
	for(int currentChar=0; currentChar < nameLength; --nameLength, ++currentChar)
	{
		// copy 1st letter in the array index into temp
		char temp = name[currentChar]; 
		// copy last letter in the array index into the 1st array index
		name[currentChar] = name[nameLength];
		// copy temp into last array index
		name[nameLength] = temp;
	}
}// http://programmingnotes.org/

SAMPLE OUTPUT

Enter your name: My Programming Notes
Your name reversed is: setoN gnimmargorP yM

======= REVERSE A CHARACTER SEQUENCE USING A STACK =======

The following will demonstrate (1) method which reverses a character sequence using the STL stack.





		
		
			#8 - Reverse Char Sequence Using Stack
			
C++
			
			#include <iostream>
#include <stack>
using namespace std;

// function prototypes
void Reverse(stack<char> &name);

int main()
{ 
	// using the internal system stack
	stack<char> name;
	char singleChar;
	
	cout<<"Enter your name: ";
	
	while(cin.get(singleChar) && singleChar != '\n')
	{
		name.push(singleChar);
	}
	
	cout<<"\nYour name reversed is: ";

	// function declaration
	Reverse(name);
	cout<<endl;

	return 0;
}// end of main

void Reverse(stack<char> &name)
{
	while(!name.empty())
	{
		cout << name.top();
		name.pop();
	}
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
				
						#include <iostream>
#include <stack>
using namespace std;
 
// function prototypes
void Reverse(stack<char> &name);
 
int main()
{ 
	// using the internal system stack
	stack<char> name;
	char singleChar;
	
	cout<<"Enter your name: ";
	
	while(cin.get(singleChar) && singleChar != '\n')
	{
		name.push(singleChar);
	}
	
	cout<<"\nYour name reversed is: ";
 
	// function declaration
	Reverse(name);
	cout<<endl;
 
	return 0;
}// end of main
 
void Reverse(stack<char> &name)
{
	while(!name.empty())
	{
		cout << name.top();
		name.pop();
	}
}// http://programmingnotes.org/

SAMPLE OUTPUT

Enter your name: My Programming Notes
Your name reversed is: setoN gnimmargorP yM

Tag Archives: stack

C++ || Simple Palindrome Checker Using A Stack & Queue Using C++

C++ || Snippet – Custom Template Linked List Sample Code

C++ || Snippet – Palindrome Checker Using A Stack & Queue

C++ || Stack – Using A Stack, Determine If A Set Of Parentheses Is Well-Formed

C++ || Snippet – Linked List Custom Template Stack Sample Code

C++ || Stack Based Postfix Evaluation (Single Digit)

C++ || Snippet – Array Based Custom Template Stack Sample Code

C++ || 8 Different Ways To Reverse A String/Character Array In C++

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories