第一条：
(1) using array or link structure to implement the polynomial’s ADD operation.
State clearly the implementation and its time complexity.
(2) Stack can be used to convert infix expression to postfix expression. You are required to finish following:
a. Implement a stack and its PUSH / POP operations; state clearly its implementation.
b. Operation of converting infix to postfix, state its time complexity.
c. calculate the value of the postfix expression with your implementation, state its time complexity.
第二条：
(1) Prove that for any nonempty binary tree, n0 = n2 + 1 where n0 is the number of leaf nodes and n2 the number of nodes of degree 2.
(2) Using linked representation following to create a binary tree. The program you implemented should accept the data to ‘data’ field from input.
typedef struct node *tree_ptr;
typedef struct node
{
int data;
tree_ptr left_child,right_child;
}
Implement the program of inorder traversal, preorder traversal and postorder traversal. And analyze their time complexity.
(3) Consider a message comprised only of the following symbols: {C, A, T, P}, assume message is: CCT PAT TTP CTP CPA, use the Huffman algorithm to encode the symbols by frequency.
Implement the program to create this tree[
求各位大大帮帮忙！快死人了！

////////////////////////////////////////////////
// This is the answer to question 1.
////////////////////////////////////////////////

#include <iostream>
#include <stack>
#include <list>
#include <cmath>
#define NDEBUG

using namespace std;

double toi(char*, int*);
int test(char);

stack<double, list<double> > num;
stack<char, list<char> > op;

int main()
{

op.push('\0');

char exp[100];
cin.getline(exp, 100, '\n');

int n = 0;
int len;
len = strlen(exp);

#ifndef NDEBUG

cout << exp << endl;
#endif

while (exp[n] != '\0')
{
if (exp[n] == ' ')
{
for (int nn = n + 1;nn < len; nn++)
exp[nn-1] = exp[nn];
len--;
n--;
}
n++;
}
exp[len] = '\0';

#ifndef NDEBUG

cout << exp;
#endif

int k;
k = 0;

int flag = 1;

char c;
c = exp[0];

while (flag)
{
if (c >= '0' && c <= '9' || c == '.')
num.push(toi(exp, &k));
else if (c == '(' || test(c) > test(op.top()))
{
op.push(c);
k++;
}
else if (c == '\0' && op.top() == '\0')
flag = 0;
else if (c == ')' && op.top() == '(')
{
op.pop();
k++;
}
else if (test(c) <= test(op.top()))
{
double y = num.top();
num.pop();
double x = num.top();
num.pop();
c = op.top();
op.pop();
switch (c)
{
case '*': x *= y; break;
case '/': x /= y; break;
case '+': x += y; break;
case '-': x -= y; break;
case '^': x = pow(x, y); break;
default : cout << "Error!!\n"; break;
}
num.push(x);
}
c = exp[k];
}
cout << endl << exp << " = " << num.top() << endl << endl;

system("pause");

return 0;
}

double toi(char* c, int* k)
{
double x, y = 1.0;
int flag = 1;
char s;
x = 0.0;
s = c[*k];
while (s >= '0' && s <= '9' || s == '.')
{
*k = *k + 1;
if (s >= '0' && s <= '9')
if (flag == 1)
x = 10*x + (s - 48);
else
{
y *= 0.1;
x += y * (s - 48);
}
else
flag = 0;
s = c[*k];
}

return (x);
}

int test(char c)
{
int x;
switch (c)
{
case '^' : x = 3; break;
case '*' : x = 2; break;
case '/' : x = 2; break;
case '+' : x = 1; break;
case '-' : x = 1; break;
case '(' : x = 0; break;
case ')' : x = 0; break;
case '\0' : x = -1; break;
}
return (x);
}

////////////////////////////////////////////////
// This is the answer to question 1.
////////////////////////////////////////////////