数据结构 中缀式转后缀式（编译器：VS）

数据结构 中缀式转后缀式

原理：
1.建立一个栈用来储存操作符
2.将中缀式从左到右扫描，如果是数字就存进一个字符串，如果是操作符就遵从以下原则：
若op的优先级高于栈顶的操作符，将该op压栈
若op的优先级低于栈顶的操作符，将栈中的操作符弹出直到栈顶的操作符优先级低于该op，并将弹出的操作符存入刚在的字符串中
若op为“（”，直接压栈
若op为“）”,弹栈直到遇到“（”,且括号舍弃，不存入字符串（后缀式中不具有括号）
3.中缀式扫描完后，将栈中剩余的操作符弹出，存入字符串中

头文件：1.h

头文件：2.h(栈的定义)

头文件：3.h（各种函数的实现）
#include “1.h”
#include “2.h”
Status InitStack(SqStack &S)
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base) return OVERFLOW;
S.top = S.base;//当前为空
S.stacksize = STACK_INIT_SIZE;
return OK;
}

Status Push(SqStack &S, SElemType e)
{
SElemType newbase;
if ((S.top - S.base) >= S.stacksize)
{
newbase = (SElemType)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType));
if (!newbase) return OVERFLOW;
S.base = newbase;
S.top = S.base + S.stacksize;
S.stacksize = STACK_INIT_SIZE + STACKINCREMENT;

}
*S.top = e;
S.top++;
return OK;

}

Status StackEmpty(SqStack S)
{
return (S.base == S.top);
}

Status Pop(SqStack &S, SElemType &e)
{
if (S.base == S.top) return ERROR;
S.top–;
e = *S.top;
return OK;
}
Status GetTop(SqStack S, SElemType &e)
{
if (S.base == S.top) return ERROR;

e = *(S.top - 1);
return OK;

}
void Transform(char s[],char d[])//中缀转后缀
{
SqStack S;
InitStack(S);
SElemType e;//记录栈顶的值
int i,j=0;
for (i = 0; s[i] != ‘\0’; i++)
{
if (s[i] >= ‘0’&&s[i] <= ‘9’)
{
d[j] = s[i];
j++;
}

	if ( s[i] == '(')
			Push(S, s[i]);
	if (s[i] == '+' || s[i] == '-')
	{
			
			if (!GetTop(S, e))
				Push(S, s[i]);
			while (e=='*'||e=='/')
			{
				Pop(S, d[j]);
				j++;
				GetTop(S, e);
				if (StackEmpty(S))
					break;
			}
			Push(S, s[i]);
			
			
	}
	if (s[i] == '*' || s[i] == '/')
	{
			Push(S, s[i]);
	}
	if (s[i] == ')')
	{
		GetTop(S, e);
		while (e != '(')
		{
			Pop(S, d[j]);
			j++;
			GetTop(S, e);
			if (StackEmpty(S))
				continue;
		}
		Pop(S, e);
	}
	

}
while (!StackEmpty(S))
{
	Pop(S, d[j]);
	j++;
}
d[j] = '\0';

}
void Show(char d[])//输出后缀式
{
int i = 0;
for (; d[i] != ‘\0’;i++)
{
cout << d[i]<<" ";
}
}

源函数：
#include “3.h”
int main()
{
char s[100], d[100];//d储存后缀式
cout << “请输入表达式：”;
cin >> s;
Show(s);
Transform(s, d);
cout << “后缀式为：”;
Show(d);//将中缀式转换为后缀式

}