Untitled
unknown
plain_text
a month ago
10 kB
1
Indexable
#include <iostream>
#include "main.h"
using namespace std;
struct Node
{
int data;
Node* next;
Node* start;
};
void push(Node* &stack, int data)
{
Node* newnode = new Node;
//std::cout << "Test " << data << endl;
newnode->data = data;
//std::cout << "Push " << data << endl;
if (stack != nullptr)
{
newnode->next = stack;
newnode->start = stack->start;
stack = newnode;
}
else
{
//std::cout << "pierwszy element\n";
stack = newnode;
stack->start = stack;
stack->next = nullptr;
}
//newnode->next = stack;
//std::cout << "push " << endl;
}
void pop(Node* &stack)
{
if (stack != nullptr && stack->next != nullptr)
{
//std::cout << "Popping " << stack->data << endl;
Node* prev = stack;
stack = stack->next;
delete prev;
}
else if (stack != nullptr && stack->next == nullptr) // ostatni element
{
//std::cout << "Popping last element: " << stack->data << endl;
delete stack;
stack = nullptr;
}
else
{
std::cout << "Nothing to pop, stack is empty " << endl;
}
}
int topEl(Node* stack)
{
return stack->data;
}
bool isEmpty(Node* stack)
{
if (stack == nullptr)
{
return true;
}
return false;
}
int getStackSize(Node* stack)
{
//std::cout << "getStackSize" << endl;
int stacksize = 0;
Node* counter = stack;
while (counter != nullptr)
{
stacksize++;
//std::cout << "Counter: " << counter->data << endl;
counter = counter->next;
}
return stacksize;
}
int test = 0;
void printStack(Node* stack)
{
if (stack != nullptr)
{
std::cout << "printStack stack->data: " << stack->data << endl;
//std::cout << "printStack stack->start: " << stack->start << endl;
test++;
/*if (test > 10)
{
test = 0;
return;
}*/
if (stack->next != nullptr)
{
printStack(stack->next);
}
}
}
void printStack2(Node* stack)
{
if (stack != nullptr)
{
std::cout << char(stack->data);
//std::cout << "printStack stack->start: " << stack->start << endl;
test++;
/*if (test > 10)
{
test = 0;
return;
}*/
if (stack->next != nullptr)
{
printStack2(stack->next);
}
}
}
void reverse(Node* &stack)
{
std::cout << "Reversing stack" << endl;
Node* newstack = nullptr;
while (stack != nullptr)
{
push(newstack, topEl(stack));
pop(stack);
}
stack = newstack;
newstack = nullptr;
delete newstack;
}
void UpdateStart(Node* stack)
{
if (stack->next == nullptr)
{
return;
}
else
{
stack->next->start = stack->start;
UpdateStart(stack->next);
}
}
Node* merge(Node* A, Node* B)
{
std::cout << "Merging stacks" << endl;
B->start->next = A;
UpdateStart(B);
delete A;
return B;
}
Node* CreateStack()
{
Node* stack = new Node;
stack->start = stack;
stack->next = nullptr;
return stack;
}
void Sort(Node*& stack)
{
Node* pomocniczy = nullptr;
while (stack != nullptr)
{
printStack(pomocniczy);
// pobieramy gore, sciagamy z oryginalnego stosu
int gora = topEl(stack);
std::cout << "Pobrana gora: " << gora << endl;
pop(stack);
// sciagamy ze stosu pomocniczego wszystko to, co jest mniejsze niz pobrany element, wrzucamy na stos oryginalny
while (pomocniczy != nullptr && pomocniczy->data < gora)
{
int gora_p = topEl(pomocniczy);
pop(pomocniczy);
push(stack, gora_p);
}
printStack(pomocniczy);
// stos pomocnicy - wrzucamy wybrany element
push(pomocniczy, gora);
// z powrotem wrzucamy na stos pomocniczy to co wrzucilismy do oryginalnego
while (stack != nullptr && stack->data <= pomocniczy->data)
{
int gora_g = topEl(stack);
pop(stack);
push(pomocniczy, gora_g);
}
printStack(stack);
printStack(pomocniczy);
}
delete stack;
stack = pomocniczy;
delete pomocniczy;
}
void printAsMermaidGraph(Node* stack)
{
std::cout << "graph LR;" << endl;
Node* iter = stack;
//string l2 = ""
int counter = 1;
std::cout << "stos:::nonnode-.->";
while (iter != nullptr)
{
std::cout << "id" << counter << "[" << iter->data << "]:::node-->";
iter = iter->next;
counter++;
}
std::cout << "nullptr:::nonnode;" << endl;
std::cout << "classDef node fill:#fff,stroke:#333,color:#333" << endl;
std::cout << "classDef nonnode fill:#fff,stroke:#fff,color:#A3303B" << endl;
// Uzupe³nij kod tutaj.
}
int sila(char c)
{
if (c == '^')
{
return 3;
}
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
bool is_operand(char c)
{
if (c == '/' || c == '*' || c == '^' || c == '+' || c == '-' || c == '(' || c == ')')
{
return false;
}
return true;
}
std::string infixtopostfix(std::string infix)
{
Node* stos = nullptr;
std::string postfix = "";
std::cout << "INFIXTOPOSTFIX" << endl;
for (char currentchar : infix)
{
std::cout << currentchar << " " << endl;
std::cout << "Stos: ";
printStack2(stos);
std::cout << endl;
// Je¿eli operand
if (is_operand(currentchar))
{
postfix += currentchar;
//std::cout << postfix << " is the postfix" << endl;
}
else if (currentchar == '(')
{
push(stos, currentchar);
}
else if (currentchar == ')')
{
while (stos != nullptr && topEl(stos) != '(')
{
postfix += topEl(stos);
pop(stos);
}
if (stos != nullptr && topEl(stos) == '(')
pop(stos); // Remove '('
}
else // Je¿eli nie operand
{
int currentsila = sila(currentchar); // Je¿eli na stosie jest mniejsza sila, stos to ( albo stos jest pusty:
if (stos == nullptr || sila(topEl(stos)) < currentsila || topEl(stos) == '(')
{
push(stos, currentchar);
}
else
{
while(stos != nullptr && sila(topEl(stos)) >= currentsila)
{
char topel = topEl(stos);
//std::cout << "??? :---- " << topel << endl;
if (topel != ')' && topel != '(')
{
postfix += topel;
}
pop(stos);
}
push(stos, currentchar);
}
}
// wrzucamy co zostalo na stosie
}
while (stos != nullptr)
{
if (topEl(stos) != '(' && topEl(stos) != ')')
{
postfix += topEl(stos);
}
pop(stos);
}
return postfix;
}
int main()
{
// Testing push, pop, topel, size
std::cout << "----TEST1----" << endl;
Node* stack = nullptr;
cout << "Empty: " << isEmpty(stack) << endl;
push(stack, 1);
push(stack, 2);
push(stack, 3);
push(stack, 4);
pop(stack);
push(stack, 8);
printStack(stack);
cout << "Size: " << getStackSize(stack) << endl;
cout << "TOPEL: " << topEl(stack) << endl;
pop(stack);
cout << "TOPEL: " << topEl(stack) << endl;
pop(stack);
pop(stack);
pop(stack);
pop(stack);
pop(stack);
pop(stack);
pop(stack);
//pop(stack);
cout << "Size: " << getStackSize(stack) << endl;
// Testing reverse
std::cout << "----TEST2----" << endl;
Node* stack2 = nullptr;
push(stack2, 1);
push(stack2, 2);
push(stack2, 3);
push(stack2, 4);
push(stack2, 5);
push(stack2, 6);
push(stack2, 7);
printStack(stack2);
reverse(stack2);
printStack(stack2);
reverse(stack2);
printStack(stack2);
// Testing merge
std::cout << "----TEST3----" << endl;
Node* teststack1 = nullptr;
push(teststack1, 10);
push(teststack1, 11);
push(teststack1, 12);
push(teststack1, 13);
Node* teststack2 = nullptr;
push(teststack2, 20);
push(teststack2, 21);
push(teststack2, 22);
push(teststack2, 23);
std::cout << "1 stos" << endl;
printStack(teststack1);
std::cout << "2 stos" << endl;
printStack(teststack2);
Node* mergedstack = merge(teststack1, teststack2);
std::cout << "polaczone stosy" << endl;
printStack(mergedstack);
// Testing sort
std::cout << "----TEST4----" << endl;
Node* sortstack1 = nullptr;
push(sortstack1, 3);
push(sortstack1, 1);
push(sortstack1, 8);
push(sortstack1, 4);
push(sortstack1, 12);
push(sortstack1, 5);
push(sortstack1, 6);
push(sortstack1, 9);
push(sortstack1, 0);
push(sortstack1, 2);
push(sortstack1, 6);
push(sortstack1, 11);
printStack(sortstack1);
Sort(sortstack1);
std::cout << "posortowalismy stos" << endl;
printStack(sortstack1);
// Testing sort
std::cout << "----TEST5----" << endl;
printAsMermaidGraph(sortstack1);
std::cout << "----TEST6----" << endl;
std::string test = "a*b*c+d*f+g+h";
std::string postfix = infixtopostfix(test);
std::cout << test << endl;
std::cout << postfix << endl;
std::string test2 = "a+b*(c^d-e)^(f+g*h)-i";
std::string postfix2 = infixtopostfix(test2);
std::cout << test2 << endl;
std::cout << postfix2 << endl;
return 0;
}
/* todo
infixToPostfixViaStack
*/
Editor is loading...
Leave a Comment