`

重学数据结构006——中缀表达式转后缀表达式

阅读更多

        我们在数学中常见的计算式,例如2+(3*4)叫做中缀表达式。表达式中涉及到了多个运算符,而运算符之间是有优先级的。计算机在计算并且处理这种表达式时,需要将中缀表达式转换成后缀表达式,然后再进行计算。

        中缀表达式转后缀表达式遵循以下原则:

        1.遇到操作数,直接输出;

        2.栈为空时,遇到运算符,入栈;

        3.遇到左括号,将其入栈;

        4.遇到右括号,执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出;

        5.遇到其他运算符'+''-''*''/'时,弹出所有优先级大于或等于该运算符的栈顶元素,然后将该运算符入栈;

        6.最终将栈中的元素依次出栈,输出。

        经过上面的步骤,得到的输出既是转换得到的后缀表达式。

        举例:a+b*c+(d*e+f)*g    ---------> abc*+de*f+g*+

遇到a,直接输出:

遇到+,此时栈为空,入栈:

遇到b,直接输出:

遇到*,优先级大于栈顶符号优先级,入栈:

遇到c,输出:

遇到+,目前站内的*与+优先级都大于或等于它,因此将栈内的*,+依次弹出并且输出,并且将遇到的这个+入栈:

遇到(,将其入栈:

遇到d,直接输出:

遇到*,由于*的优先级高于处在栈中的(,因此*入栈:

遇到e,直接输出:

遇到+,栈顶的*优先级高于+,但是栈内的(低于+,将*出栈输出,+入栈:

遇到f,直接输出:

遇到),弹出栈顶元素并且输出,直到弹出(才结束,在这里也就是弹出+输出,弹出(不输出:

遇到*,优先级高于栈顶+,将*入栈:

遇到g,直接输出:

此时已经没有新的字符了,依次出栈并输出操作直到栈为空:

明白了这个过程,现在就需要用代码实现了。对于各种运算符的优先级,可以使用整数来表示运算符的级别。可以定义一个函数来返回各种符号的优先级数字:

/*****************************************************************
*根据字符该字符是否在栈中,返回该字符的优先级。
*这里只处理+、-、*、/、(、)这些符号。
*需要注意的是:如果(在栈中,它的优先级是最低的,不在栈中则是最高的
*@param c:需要判断的字符
*@param flag:字符是否在栈中,0表示在栈中,1表示不在栈中
*****************************************************************/
int GetPrecedence(char c,int flag)
{
	if(c=='+' || c=='-')
	{
		return 1;
	}
	else if(c=='*' || c=='/')
	{
		return 2;
	}
	else if(c=='(' && flag==0)
	{
		return 0;
	}
	else if(c=='(' && flag==1)
	{
		return 3;
	}
	else
	{
		fprintf(stderr,"Input char is invalid!\n");
		return -1;
	}
}

 还可以定义一个函数来判断当前遇到的是运算符还是操作数:

/****************************************************************
*判断一个字符是不是运算符
*如果是合法的运算符+、-、*、/、(、)则返回0,否则返回1
****************************************************************/
int IsOperator(char c)
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')')
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

        完整的代码如下:

#include <stdio.h>
#include <stdlib.h>
#define ElementType char

typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
typedef struct Node
{
	ElementType Element;
	PtrToNode Next;
};

int IsEmpty(Stack S);
Stack CreateStack();
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X,Stack S);
ElementType Top(Stack S);
void Pop(Stack S);

//判断栈是否为空
int IsEmpty(Stack S)
{
	return S->Next == NULL;
}
//创建链栈
Stack CreateStack()
{
	Stack S = malloc(sizeof(struct Node));
	if(S == NULL)
	{
		printf("No enough memory!");
		return NULL;
	}
	S->Next = NULL;
	MakeEmpty(S);
	return S;
}
//清空栈
void MakeEmpty(Stack S)
{
	if(S == NULL)
	{
		printf("Use CreateStack First!");
	}
	else
	{
		while(!IsEmpty(S))
		{
			Pop(S);
		}
	}
}
//进栈
void Push(ElementType X,Stack S)
{
	PtrToNode Tmp;
	Tmp = malloc(sizeof(struct Node));
	if(Tmp != NULL)
	{
		Tmp->Element = X;
		Tmp->Next = S->Next;
		S->Next = Tmp;
	}
	else
	{
		printf("Out of space!");
	}
}
//出栈
void Pop(Stack S)
{
	
	if(IsEmpty(S))
	{
		printf("The Stack is Empty!");
	}
	else
	{
		PtrToNode Tmp = S->Next;
		S->Next = Tmp->Next;
		free(Tmp);
	}
}
//返回栈顶元素
ElementType Top(Stack S)
{
	if(IsEmpty(S))
	{
		printf("The stack is empty!");
		return 0;
	}
	else
	{
		return S->Next->Element;
	}
}

/*****************************************************************
*根据字符该字符是否在栈中,返回该字符的优先级。
*这里只处理+、-、*、/、(、)这些符号。
*需要注意的是:如果(在栈中,它的优先级是最低的,不在栈中则是最高的
*@param c:需要判断的字符
*@param flag:字符是否在栈中,0表示在栈中,1表示不在栈中
*****************************************************************/
int GetPrecedence(char c,int flag)
{
	if(c=='+' || c=='-')
	{
		return 1;
	}
	else if(c=='*' || c=='/')
	{
		return 2;
	}
	else if(c=='(' && flag==0)
	{
		return 0;
	}
	else if(c=='(' && flag==1)
	{
		return 3;
	}
	else
	{
		fprintf(stderr,"Input char is invalid!\n");
		return -1;
	}
}

/****************************************************************
*判断一个字符是不是运算符
*如果是合法的运算符+、-、*、/、(、)则返回0,否则返回1
****************************************************************/
int IsOperator(char c)
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')')
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

char Output[50];
//中缀表达式转成后缀表达式
char* InfixToPostfix(char *ch,Stack S)
{
	
	int index=0;
	char c;
	while((c=*ch) != '\0')
	{
		//不是运算符,将该字符放进输出字符数组中。
		if(IsOperator(c)==1)
		{
			Output[index++] = c;
			ch++;
		}
		//是运算符
		else
		{
			//如果此时栈为空,运算符进栈
			if(IsEmpty(S))
			{
				Push(c,S);
				ch++;
				continue;
			}
			else
			{
				if(c==')')	
				{
					while(!IsEmpty(S) && Top(S) != '(')
					{
						Output[index++] = Top(S);
						Pop(S);
					}
					Pop(S);
					ch++;
					continue;
				}
				else
				{
					int outPrecedence = GetPrecedence(c,1);
					while(!IsEmpty(S) && GetPrecedence(Top(S),0) >= outPrecedence)
					{
						Output[index++] = Top(S);
						Pop(S);
					}
					Push(c,S);
					ch++;
					continue;
				}
			}
		}
	}
	while(!IsEmpty(S))
	{
		Output[index++] = Top(S);
		Pop(S);
	}
	Output[index] = '\0';
	return Output;
}



int main(void)
{
	Stack S = CreateStack();
	char *charSequence = "1+2*3+(4*5+6)*7";
	char tmp;
	char *out = InfixToPostfix(charSequence,S);
	
	
	while((tmp=*out)!='\0')
	{
		printf("%c ",tmp);
		out++;
	}
	printf("\n");
	return 0;
}

 ok,终于基本上把教材上栈的部分学习完了。

 

 

0
0
分享到:
评论

相关推荐

    数据结构的中缀表达式转后缀表达式使用C++实现

    本文将详细讨论如何使用C++实现数据结构中的一个重要概念——中缀表达式转化为后缀表达式,也被称为逆波兰表示法。这个过程涉及到堆栈这一重要的数据结构。 中缀表达式是我们日常生活中常见的数学表达式形式,例如 ...

    数据结构(中缀表达式转后缀表达式)

    /*程序由本人编译,并且经过多次测试,正确无误!目前该转换算法只支持数字在0至9之间的+-*/四元运算转换.*/ /**************程序员信息 ***************东北大学*******************东大很厉害**************** ...

    编译原理——中缀表达式转后缀表达式

    先写词法分析的源文件,用正则表达式表示出需要识别的字符,例如数字,乘法,加法和括号,如果识别到其他非法字符需要报错,用flex生成lex.yy.c文件。语法分析用LR方法进行语法分析,LR方法需要先根据文法构造自动机...

    c语言实现中缀表达式转后缀并求值

    c语言实现中缀表达式转后缀表达式并求得计算结果,用顺序栈结构。 当输入者输入错误信息的时候需要报错,并说明错误的种类。

    C语言实现中缀表达式转化后缀表达式

    利用C语言实现中缀表达式转化为后缀表达式!!利用栈。

    数据结构算法:中缀表达式转化为后缀表达式.doc

    数据结构算法:中缀表达式转化为后缀表达式.doc 详细的论述和代码!

    中缀表达式转后缀表达式计算

    编译系统对中缀表达式的处理方法是先把它转换为后后缀表达式.在后缀表达式中,运算符位于两个操作数的后面,并且没有括号,其运算符的次序就是其执行运算的次序。后缀表达式计算过程的规则非常简单:从左到右依次扫描,...

    将中缀表达式转换为后缀表达式并求值实验报告

    总之,这个实验报告的核心是实现中缀表达式到后缀表达式的转换以及基于后缀表达式的计算,它涉及到数据结构中的栈操作,以及对运算符优先级的理解。这个过程对于理解计算机如何解析和计算数学表达式非常有帮助。

    中缀表达式转后缀表达式源程序(二叉树)

    一个简单的算法,利用栈实现中缀表达式与后缀表达式的转换

    中缀表达式转后缀表达式

    用栈实现中缀表达式转为后缀表达式,规定了各个符号的优先级,可以说是对栈概念的深入理解

    数据结构实验报告-栈与队列-中缀表达式转换为后缀式5分-实验内容及要求.docx

    为了实现中缀表达式到后缀表达式的转换,实验采用了栈这一数据结构。具体的设计如下: - **栈的实现**:使用一组连续的存储单元来存储栈内的所有结构体`node`。每个`node`包含两个成员: - `char op`:用于存储...

    c语言实现中缀表达式向后缀表达式转换

    本篇文章将详细探讨如何通过C语言实现中缀表达式到后缀表达式转换的过程,并具体分析所涉及的关键算法与数据结构。 #### 中缀表达式与后缀表达式简介 - **中缀表达式**:我们日常使用的数学表达式,如 `3 + 4 * 2`...

    表达式树 中缀表达式转后缀

    总结来说,中缀表达式转后缀表达式是编译原理中的基本操作,它涉及到了栈数据结构、运算符优先级以及表达式树的构建。通过这种方法,我们可以更高效地计算和解析数学表达式,这对于计算机程序设计,尤其是编译器和...

    栈实现中缀表达式到后缀表达式的转换

    本主题将深入探讨如何使用栈数据结构来实现中缀表达式到后缀表达式的转换,主要以C语言编写。 栈是一种具有“后进先出”(LIFO)特性的数据结构,非常适合处理运算符的优先级。转换过程主要分为两个步骤:扫描中缀...

    中缀表达式转后缀表达式树

    通过中缀表达式转后缀表达式,我们可以很容易地构建这棵树,因为后缀表达式的顺序就是操作符对操作数的计算顺序。 在实现这个算法时,通常会使用一个数据结构,如二叉树或者链表,来存储表达式树。在控制台中画出...

    数据结构 中缀表达式转后缀表达式

    总结来说,中缀表达式转后缀表达式是通过栈这一数据结构实现的,主要涉及对运算符优先级的处理,以及正确处理括号的嵌套。转换后的后缀表达式可简化计算过程,因为无需考虑运算符的优先级,只需顺序处理即可。

    中缀表达式转成后缀表达式并输出计算结果

    用户输入中缀表达式,程序输出后缀表达式并输出计算结果

    自定义栈中缀表达式转换为后缀表达式并求值

    2. **中缀表达式转后缀表达式** (`class Middle_expressionToPost_expression`) 3. **后缀表达式求值** (`class Post_expression_value`) 每个组件的功能如下: 1. **自定义栈**: - 主要功能是管理运算符的入栈和...

Global site tag (gtag.js) - Google Analytics