SHARE
TWEET

Untitled

a guest Dec 11th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <utility>
  4. #include "BinTree.h"
  5. using namespace std;
  6. //Problem 1:
  7. //Create a custom build linked list class to implement a stack and create
  8. //a push, pop, and peek function for the class.
  9. //The Node class for the linked list should have a string variable and a next pointer.
  10. /*
  11. template<typename T>
  12. struct Node {
  13.     T data;
  14.     Node* next = nullptr;
  15. };
  16.  
  17. template<typename T>
  18. class LinkedList {
  19. private:
  20.     Node<T>* head;
  21. public:
  22.     LinkedList() {
  23.         head = nullptr;
  24.     }
  25.  
  26.  
  27.  
  28.     void pushFIFO(string& data) {
  29.         Node<T>* n = new Node<T>;
  30.         n->data = data;
  31.  
  32.         if (head == nullptr) {
  33.             head = n;
  34.             return;
  35.         }
  36.         Node<T>* cur = head;
  37.         while (cur->next != nullptr) {
  38.             cur = cur->next;
  39.         }
  40.         cur->next = n;
  41.     }
  42.  
  43.     void pushLIFO(T data) {
  44.         Node<T>* n = new Node<T>;
  45.         n->data = std::move(data);
  46.         n->next = head;
  47.         head = n;
  48.     }
  49.  
  50.     T pop() {
  51.         Node<T>* oldHead = head;
  52.         T result = oldHead->data;
  53.  
  54.         head = oldHead->next;
  55.         delete oldHead;
  56.         return result;
  57.     }
  58.  
  59.     T peek() {
  60.         if (head == nullptr) {
  61.             T e;
  62.             return e;
  63.         }
  64.         return head->data;
  65.     }
  66. };
  67.  
  68. //Write a function outside of the linked list and node classes to convert
  69. //postfix expressions into prefix expressions using a stack.
  70. string convert(string expression) {
  71.     LinkedList<string> stack;
  72.     for (char c : expression) {
  73.         if (c >= '0' && c <= '9') {
  74.             string s;
  75.             s += c;
  76.             stack.pushLIFO(s);
  77.         } else {
  78.             string s;
  79.             s.insert(0, stack.pop());
  80.             s.insert(0, stack.pop());
  81.             string a;
  82.             a += c;
  83.             s.insert(0, a);
  84.             stack.pushLIFO(s);
  85.         }
  86.     }
  87.     return stack.pop();
  88. }
  89.  
  90. double evaluatePrefix(string expression) {
  91.     LinkedList<double> numStack;
  92.     LinkedList<char> opStack;
  93.     for (char c : expression) {
  94.         if (c >= '0' && c <= '9') {
  95.             double num = 1.0 * ((int) c - (int) '0');
  96.             if (numStack.peek()) {
  97.                 //operating
  98.                 double num0 = numStack.pop();
  99.                 char op = opStack.pop();
  100.                 double result;
  101.                 switch (op) {
  102.                     case '+':
  103.                         result = num0 + num;
  104.                         break;
  105.                     case '-':
  106.                         result = num0 - num;
  107.                         break;
  108.                     case '/':
  109.                         result = num0 / num;
  110.                         break;
  111.                     case '*':
  112.                         result = num0 * num;
  113.                         break;
  114.                     default:
  115.                         cout << "error";
  116.                         break;
  117.                 }
  118.                 numStack.pushLIFO(result);
  119.             }
  120.         } else {
  121.             opStack.pushLIFO(c);
  122.         }
  123.     }
  124.     return numStack.pop();
  125. }
  126.  
  127. int main() {
  128.     string prefix = "42$3*3-84/11+/+";
  129.     cout << convert(prefix);
  130.     string exp = "*+-4236";
  131.     cout << endl << evaluatePrefix(exp);
  132.  
  133.  
  134.     return 0;
  135. }*/
  136.  
  137. int main() {
  138.  
  139. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top