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
|
class Node
{
public:
int value;
int next;
Node(int number, int next)
:value(value), next(next){}
};
Node Comparisons(int number, vector<int> StackTop, Node last_node, vector<Node> node_list)
{
bool new_stack = true;
for (int i = 0; i < StackTop.size(); i++)
{
if (number < StackTop[i])
{
StackTop[i] = number;
if(i == 0)
{
Node n1 = Node(number, 0);
node_list.push_back(n1);
}
else
{
Node n1 = Node(number, StackTop[i-1]);
node_list.push_back(n1);
}
i = StackTop.size();
new_stack = false;
}
if (new_stack)
{
StackTop.push_back(number);
Node last_node = Node(number, StackTop[i-1]);
node_list.push_back(last_node);
}
}
return last_node;
}
void PrintSequence (Node last_node, vector<Node> node_list)
{
cout<<last_node.value<<" ";
Node current_node = last_node;
while (current_node.next != 0)
{
for (int i = 0; i < node_list.size(); i++)
{
if (node_list[i].value == current_node.next)
{
cout<<node_list[i].value<<" ";
current_node = node_list[i];
i += node_list.size() - i;
}
}
}
}
void main()
{
ifstream fin("RandomUpSeq.dat");
if (!fin)
{
cout<<"Could not open input file.\n";
}
keep_window_open();
string number;
string data;
getline(fin, data);
stringstream string(data);
vector<int> StackTop;
Node last_node = Node(0,0);
vector<Node> node_list;
while(getline(string, number, ','))
{
int input = atoi(number.c_str());
last_node = Comparisons(input, StackTop, last_node, node_list);
}
fin.close();
PrintSequence(last_node, node_list);
}
|