目录

• 一. 栈的概述
• 二. 二进制计算器的实现
• • 1. 二进制数转换为其他进制的流程
  • 2. 如何利用顺序栈完成上述步骤
• 三. 代码实现
• • 1. 栈的基本操作
  • • 1). 栈的顺序存储结构
    • 2). 初始化栈
    • 3). 入栈(栈满，利用realloc函数增容)
    • 4). 出栈
  • 2. 进制转换器代码实现
  • • 1). 二进制转换为八进制
    • 2). 二进制转换为十六进制
    • 3). 二进制转换为十进制

一. 栈的概述

  栈是一种先进后出的数据结构，最后进去的元素最先出来。在栈中，仅允许在栈的一端进行操作，即从栈顶插入元素，栈顶取出元素。

二. 二进制计算器的实现

1. 二进制数转换为其他进制的流程

   1).在二进制数中，如何转换为其他进制数。
   这里以二进制转化位八进制数为例，当我们需要将110101101转换为八进制数时，一般以三位二进制数对应一位八进制数进行划分。当高位不够三位二进制数时，以0补全。之后利用位权表示法进行计算。

2. 如何利用顺序栈完成上述步骤

   思想与上述转换方法类似，只是在存储计算出的八进制数时略有区别。(同样利用二进制转八进制为例)

   1). 将二进制数按照顺序进行入栈。
   2). 取出三位二进制数，利用位权表示法进行计算对应八进制数。
   3). 对计算结果进行存储，这里我们是从后向前对二进制数进行处理，如果直接输出会导致输出结果 逆序 ，所以我们再一次利用栈先进后出的特性对计算结果进行存储。开辟一个新栈 将计算结果顺序入栈，再通过出栈对数据进行输出就会正常显示计算结果。
  4).在该程序中使用的结构为栈的顺序存储结构，在初始化栈时会固定栈的大小，如果栈空间不足，会利用动态扩容的方法增加栈的长度。具体实现请看下方代码。

三. 代码实现

1. 栈的基本操作

1). 栈的顺序存储结构

在这个程序中，我们使用栈的顺序存储结构。

struct sqStack
{
	ElemeType* base;
	ElemeType* top;
	int stackSize;		// 当前栈的最大容量
};

2). 初始化栈

void CreateStack(sqStack*& sq)
{
	sq->base = new ElemeType[STACK_INIT_SIZE];
	if (!sq->base)
	{
		cout << "分配空间失败" << endl;
		return;
	}

	sq->top = sq->base;
	sq->stackSize = STACK_INIT_SIZE;
}

3). 入栈(栈满，利用realloc函数增容)

realloc()函数使用时，会重新申请一块指定大小的内存空间，并将之前数据进行移入。

void StackPush(sqStack*& sq, ElemeType e)
{
	if (sq->top - sq->base >= sq->stackSize)
	{
		sq->base = (ElemeType*)realloc(sq->base, (sq->stackSize + STACKINCREAMENT) * sizeof(ElemeType));
		if (!sq->base)
		{
			cout << "增加分配空间失败" << endl;
			return;
		}

		sq->stackSize += STACKINCREAMENT;
	}

	*sq->top = e;
	sq->top++;
}

4). 出栈

int StackPop(sqStack*& sq, ElemeType& e)
{
	if (sq->top == sq->base)
	{
		cout << " 栈空" << endl;
		return 0;
	}

	e = *--(sq->top);
	return 1;
}

2. 进制转换器代码实现

1). 二进制转换为八进制

void Bin2Oct(sqStack*& sq)
{
	// 创建新栈 用来存储转换后的结果
	sqStack* sqOct = new sqStack;

	CreateStack(sqOct);

	// 取出存放二进制栈的元素 计算转换为8进制的结果
	
	for (int j = 0; j < sq->top - sq->base; j++)
	{
		ElemeType octNum = 0;

		for (int i = 0; i < 3; i++)
		{
			ElemeType e;

			if (!StackPop(sq, e))
			{
				continue;
			}
			
			// 因为输入值为字符类型，所以利用48减去元素，得到ACSII表对应字符
			int binNum = abs(48 - e);

			octNum += binNum * pow(2, i);
		}

		octNum += 48;
		// 将计算好的8进制数 入栈
		StackPush(sqOct, octNum);
	}


	cout << "转换后结果为:";
	PrintOct(sqOct);
}

2). 二进制转换为十六进制

void Bin2Oct(sqStack*& sq)
{
	// 创建新栈 用来存储转换后的结果
	sqStack* sqOct = new sqStack;

	CreateStack(sqOct);

	// 取出存放二进制栈的元素 计算转换为8进制的结果

	for (int j = 0; j < sq->top - sq->base; j++)
	{
		ElemeType octNum = 0;

		for (int i = 0; i < 4; i++)
		{
			ElemeType e;

			if (!StackPop(sq, e))
			{
				continue;
			}

			int binNum = abs(48 - e);

			octNum += binNum * pow(2, i);
		}

		octNum += 48;

		// 如果超过10则转换为字母
		if (octNum > 57)
		{
			octNum += 7;
		}

		// 将计算好的16进制数推入栈
		StackPush(sqOct, octNum);
	}


	cout << "转换后结果为:";
	PrintOct(sqOct);
}

3). 二进制转换为十进制

二进制转十进制只需要使用位权表示法算出转化总和即可，不用利用栈去存储转换结果。

int Bin2Dec(sqStack*& sq)
{
	int sum = 0;
	ElemeType e;
	int len = StackLen(*sq);

	for (int i = 0; i < len; i++)
	{
		PopStack(sq, e);
		int num = abs(48 - e);

		sum += num * pow(2, i);
	}

	return sum;
}