Guest User

Untitled

a guest
Dec 11th, 2019
113
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