change.cpp

实现LZW压缩及解压缩的程序

#include <iostream>
#include <string>
#include "LinkedStack.h"
using namespace std;

char* MidToBack(char expr[])
{
	LinkedStack<char> s;
	char* p = new char[strlen(expr)];
	int k = 0;

	for (int i=0;i<strlen(expr);i++)
	{
		if (expr[i]>=48 && expr[i]<=57)
		{
	    	p[k] = expr[i]-48;
			while (expr[i+1]>=48 && expr[i+1]<=57)
			{
				p[k] = int(p[k])*10+int(expr[++i]-48);
			}
			k++;
		}
		else if (expr[i] == '(')
		{
			s.Push(expr[i]);
			if (expr[i+1]=='-')
			{
				p[k++] = '0';
			}
		}
		else if (s.IsEmpty())
		{
			s.Push(expr[i]);
		}
		else if (expr[i] == ')')
		{
			char temp = s.Delete();
			while (temp!='(')
			{
				p[k++] = temp;
				temp = s.Delete();
			}
		}
		else if (expr[i]=='*' || expr[i]=='/')
		{
			s.Push(expr[i]);
		}
		else if (s.Top()=='*' || s.Top()=='/')
		{
			while (!s.IsEmpty() && (s.Top()=='*' || s.Top()=='/'))
			{
				p[k++] = s.Delete();
			}
			s.Push(expr[i]);
		}
		else
		{
			s.Push(expr[i]);
		}
	}
	while (!s.IsEmpty())
	{
		p[k++] = s.Delete();
	}
	p[k++] = '\0';
	return p;
}

TreeNode* ChangeToTree(char expr[])
{
	char* c = MidToBack(expr);
	LinkedStack<TreeNode*> s;
	for (int i=0;i<strlen(c);i++)
	{
		TreeNode* p = new TreeNode;
		p->data = c[i];
		if (c[i]!='+' && c[i]!='-' && c[i]!='*' && c[i]!='/')
		{
			p->firstchild = p->nextsibling = 0;
		}
		else 
		{
			p->nextsibling = s.Delete();
			if (s.Top()->data!='0')
			{
				p->firstchild = s.Delete();
			}
			else
			{
				p->firstchild = 0;
				s.Pop();
			}
		}
		s.Push(p);
	}
	return s.Delete();
}

float Calculate(TreeNode* Gen)
{
	if (Gen->data!='+' && Gen->data!='-' && Gen->data!='*' && Gen->data!='/')
	{
		return (Gen->data);
	}
	else if (Gen->data == '+')
	{
		return Calculate(Gen->firstchild)+Calculate(Gen->nextsibling);
	}
	else if (Gen->data == '-')
	{
		if (!Gen->firstchild)
		{
			return 0-Calculate(Gen->nextsibling);
		}
		else
		{
			return Calculate(Gen->firstchild)-Calculate(Gen->nextsibling);
		}	
	}
	else if (Gen->data == '*')
	{
		return Calculate(Gen->firstchild)*Calculate(Gen->nextsibling);
	}
	else
	{
		if (Calculate(Gen->nextsibling)==0)
		{
			cout<<"除 数 不 能 为 0"<<endl;
			exit(1);
		}
		return Calculate(Gen->firstchild)/Calculate(Gen->nextsibling);
	}
}