数据结构阶段二(2)

这一次我采用了链栈来实现,基本思路和上一个版本一模一样,把数据类型换为了string,也是只支持纯数字

 

点击查看代码
#include<iostream>
#include<string>
using namespace std;

// 链栈的存储结构
typedef struct StackNode
{
	string date;
	struct StackNode* next;
} StackNode, * LinkStack;

// 链栈的初始化
int InitStack(LinkStack& S)
{
	S = NULL;  //将栈顶指针置空
	return 1;
}


int Push(LinkStack& S, string e) {
	LinkStack p;
	p = new StackNode;
	if (!p)
		exit(0);
	p->date = e;
	p->next = S;
	S = p;
	return 0;
}

//出栈
int Pop(LinkStack& S, string& e) {
	LinkStack p;
	p = new StackNode;
	if (S == NULL)
		return 1;
	e = S->date;
	p = S;
	S = S->next;
	delete p;
	return 0;
}

int Linklength(LinkStack S)
{
	int num = 0;
	LinkStack q = S;
	while (q) {
		num++;
		q = q->next;
	}
	return num;
}

string noX(string num1, string num2, string oper) {
	int num_1, num_2, mid1;
	string mid;
	num_1 = atoi(num1.c_str());
	num_2 = atoi(num2.c_str());
	//开始计算最优先的lisp子表达式
	if (oper.compare("+") == 0) {
		mid1 = num_1 + num_2;
		mid = to_string(mid1);
	}
	else if (oper.compare("-") == 0) {
		mid1 = num_2 - num_1;
		mid = to_string(mid1);
	}
	else if (oper.compare("*") == 0) {
		mid1 = num_1 * num_2;
		mid = to_string(mid1);
	}
	else if (oper.compare("/") == 0) {
		mid1 = num_2 / num_1;
		mid = to_string(mid1);
	}
	else
	{
		printf("表达式有误(不识别的运算符)");
		return false;
	}
	return mid;
}

int count(LinkStack &numStack, LinkStack& operStack, string &mid) {
	int length1 = Linklength(numStack);
	int length2 = Linklength(operStack);
	string num1, num2, oper;
	if (length1 <= 1 || length2 == 0) {
		cout << "error" << endl;
	}
	else
	{
		Pop(numStack, num1);
		Pop(numStack, num2);
		Pop(operStack, oper);
		if (num1.find("x") == string::npos && num2.find("x") == string::npos) {
			mid = noX(num1, num2, oper);
		}
		if (num1.find("x") != string::npos && num2.find("x") == string::npos) {
			
		}
	}
}

int main() {
	LinkStack numStack, operStack;
	InitStack(numStack);
	InitStack(operStack);
	string mid;
    char str[200];
    gets_s(str);
    int length = strlen(str);
	for (int i = 0; i < length; i++) {
		if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
		{
			string str(1, str[i]);
			Push(operStack, str);
		}
		else if (str[i] == '(')
		{
			continue;
		}
		else if (str[i] == ',')
		{
			continue;
		}
		else if (str[i] == ')')
		{

			count(numStack, operStack, mid);
			Push(numStack, mid);
			int length1 = Linklength(numStack);
			int length2 = Linklength(operStack);
			if (length1 <= 1 && length2 == 0) {
				cout << mid << endl;
			}
		}
		else if (str[i] >= '0' && str[i] <= '9') {
			string str1(1, str[i]);
			while (true)
			{
				if (str[i + 1] >= '0' && str[i + 1] <= '9') {
					string str2(1, str[i+1]);
					str1 = str1 + str2;
					i++;
				}
				else
				{
					break;
				}
			}
			Push(numStack, str1);
		}
		else if (str[i] == 'x') {
			string str(1, str[i]);
			Push(numStack, str);
		}
		else
		{
			break;
		}
	}
}
上一篇:数据结构--链栈


下一篇:栈的链式存储的实现