汇编语言实现冒泡排序之运用标志位进行优化

问题描述

一个表达式E的后缀形式可以如下定义：
(1) 如果E是一个变量或常量，则E的后缀式是E本身。
(2) 如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’ op，这里E1’和E2’分别为E1和E2的后缀式。
(3) 如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。
如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+
(a+b)c-(a+b)/e的后缀表达式为：
(a+b)c-(a+b)/e
→((a+b)c)((a+b)/e)-
→((a+b)c)((a+b)e/)-
→(ab+c)(ab+e/)-
→ab+cab+e/-

作用
实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

示例代码（C语言）
栈__后缀表达式 Visual Studio 2019

/**
 * 数据结构 C语言 栈__后缀表达式
 * @FileName									Against_Poland.c
 * @author										W.Lionel,Esaka
 * 样例输入
 * (4+4)*2-(4+4)/2# 
 * 样例输出
 * 4 4 + 2 * 4 4 + 2 /-
 * 最终的计算结果为12 
 */

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

 /*相关宏变量*/
#define MaxBuffer 10
#define Stack_Init_Size 20
#define Stack_In_Create 10

/*定义栈结构*/
typedef char ElemType;
typedef struct {
	ElemType* Base;
	ElemType* Top;
	int StackSize;
}SeqStack;

/*初始化*/
void InitStack(SeqStack* stack)
{
	stack->Base = (ElemType*)malloc(Stack_Init_Size * sizeof(ElemType));
	if (!stack->Base)
		exit(0);
	stack->Top = stack->Base;
	stack->StackSize = Stack_Init_Size;
}

/*进栈*/
void Push(SeqStack* stack, ElemType value)
{
	if ((stack->Top - stack->Base) >= stack->StackSize)
	{
		stack->Base = (ElemType*)realloc(stack->Base, (stack->StackSize + Stack_In_Create) * sizeof(ElemType));
		if (!stack->Base)
			exit(0);
		stack->Top = stack->Base + stack->StackSize;
		stack->StackSize = stack->StackSize + Stack_In_Create;
	}
	*(stack->Top) = value;
	stack->Top++;
}

/*出栈*/
void Pop(SeqStack* stack, ElemType* value)
{
	if (stack->Top == stack->Base)
	{
		printf("栈空\n");
		return 0;
	}
	*value = *--(stack->Top);
}

/*清空栈*/
void ClearStack(SeqStack* stack)
{
	stack->Top = stack->Base;
}

/*销毁栈*/
void DestroyStack(SeqStack* stack)
{
	int i, len;
	len = stack->StackSize;
	for (i = 0; i < len; i++)
	{
		free(stack->Base);
		stack->Base++;
	}
	stack->Base = stack->Top = NULL;
	stack->StackSize = 0;
}

/*返回长度*/
int LengthStack(SeqStack stack)
{
	return(stack.Top - stack.Base);
}

/*入口*/
void main()
{
	SeqStack Stack;
	SeqStack* stack = &Stack;
	ElemType d,e,value;
	ElemType array[20] = { 0 };
	int i = 0,n;
	char c;
	InitStack(stack);

	scanf("%c", &c);
	while (c != '#')
	{
		if (c >= '0' && c <= '9')
		{
			printf("%c ", c);
			array[i] = c;
			i++;
		}
		else if (c == ')') 
		{
			Pop(stack, &value);
			while ('(' != value)
			{
				printf("%c ", value);
				array[i] = value;
				i++;
				Pop(stack, &value);
			}
		}
		else if (c == '+' || c == '-')
		{
			if ( stack->Top == stack->Base )
			{
				Push(stack, c);
			}
			else
			{
				do
				{
					Pop(stack, &value);
					if ( '(' == value)
					{
						Push(stack, value);
					}
					else
					{
						printf("%c ", value);
						array[i] = value;
						i++;
					}
				} while ( LengthStack(Stack) && '(' != value);
				Push(stack, c);
			}
		}
		else if ('*' == c || '/' == c || '(' == c)
		{
			Push(stack, c);
		}
		else 
		{
			printf("出错\n");
		}
		scanf("%c", &c);
	}
	while ( LengthStack(Stack) )
	{
		Pop(stack, &value);
		printf("%c", value);
		array[i] = value;
		i++;
	}
	printf("\n");

	n = i;
	i = 0;
	while( i < n)
	{
		if (array[i] >= '1' && array[i] <= '9')
		{
			value = (int)array[i] - 48;
			Push(stack, value);
		}

		if (array[i] == '+' || array[i] == '-' || array[i] == '/' || array[i] == '*')
		{
			switch (array[i])
			{
			case '+':
				Pop(stack, &e);
				Pop(stack, &d);
				Push(stack, d + e);
				break;
			case '-':
				Pop(stack, &e);
				Pop(stack, &d);
				Push(stack, d - e);
				break;
			case '*':
				Pop(stack, &e);
				Pop(stack, &d);
				Push(stack, d * e);
				break;
			case '/':
				Pop(stack, &e);
				Pop(stack, &d);
				Push(stack, d/e);
				break;
			}
		}
		i++;
	}
	Pop(stack, &value);
	printf("最终的计算结果为%d\n", value);
}