数据结构栈的应用逆波兰表达式

墨蓝 2022-09-19 01:30 154阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    #define STACT_INIT_SIZE   100
    #define STACTINCREMENT    10
    #define OK                1
    #define ERROR             0
    #define OVERFLOW          -2
    
    typedef char SElemType;
    
    
    typedef struct 
    {
    	SElemType *base;
    	SElemType *top;
    	int stacksize;
    }SqStack;
    
    int InitStack(SqStack &S)
    {
    	S.base = (SElemType *)malloc(STACT_INIT_SIZE * sizeof(SElemType));
    	if (!S.base)
    	{
    		exit(OVERFLOW);
    	}
    	S.top = S.base ;
    	S.stacksize = STACT_INIT_SIZE;
    	return OK;
    }
    
    int Push(SqStack &S, SElemType e)
    {
    	if (S.top - S.base >= S.stacksize)
    	{
    		S.base = (SElemType*)realloc(S.base , (S.stacksize + STACTINCREMENT) * sizeof(SElemType));
    		if (!S.base)
    		{
    			exit(OVERFLOW);
    		}
    		S.top = S.base + S.stacksize ;
    		S.stacksize += STACTINCREMENT;
    	}
    	*S.top++ = e;
    	return OK;
    }
    
    int Pop(SqStack &S, SElemType &e)
    {
    	if (S.base == S.top)
    	{
    		return ERROR;
    	}
    	e = *--S.top;
    	return OK;
    }
    
    int GetTop(SqStack S)
    {
    	if (S.base == S.top)
    	{
    		return ERROR;
    	}
    	return *(S.top-1);
    }
    
    int StackEmpty(SqStack S)
    {
    	if (S.top == S.base )
    	{
    		return 1;
    	}
    	return 0;
    }
    
    
    
    
    
    
    int DestroyStack(SqStack &S)
    {
    	free(S.base);
    	S.base = NULL;
    	S.top = NULL;
    	S.stacksize = 0;
    	return OK;
    }
    
    
    char *RPExpression(char *e)
    {/*设置两个栈，s1用来存储操作符,s2用来存储数值和从s1弹出来的操作符,即逆波兰表达式*/
    	SqStack s1,s2;
    	InitStack(s1);
    	InitStack(s2);
    	Push(s1, '#');/*假设字符'#'是运算级别最低的运算符，并压入栈s1中*/
    	char *p = e, ch;
    	int length = 0;
    	for (; *p != '\0'; p++)
    	{
    		switch (*p)
    		{
    		case '('://遇'('则直接入栈s1
    			Push(s1,*p);
    			break;
    		case ')':
    			//遇')'则将距离栈s1栈顶的最近的'('之间的运算符，逐个出栈，依次送入栈s2,此时抛弃'('
    			while (GetTop(s1) != '(')
    			{
    				Pop(s1,ch);
    				Push(s2,ch);
    			}
    			Pop(s1,ch);//将s1里面的(抛弃
    			break;
    			//遇下列运算符，则分情况讨论：
    			 //1.若当前栈s1的栈顶元素是'('，则当前运算符直接压入栈s1；
    			//2.否则，将当前运算符与栈s1的栈顶元素比较，若优先级较栈顶元素大，则直接压入栈s1中,
    			//  否则将s1栈顶元素弹出，并压入栈s2中，直到栈顶运算符的优先级别低于当前运算符，然后再将当前运算符压入栈s1中
    
    		case '+':
    		case '-':
    			for (ch = GetTop(s1); ch != '#'; ch = GetTop(s1))
    			{
    				if (ch == '(')
    				{
    					break;
    				}
    				else
    				{
    					Pop(s1,ch);
    					Push(s2,ch);
    				}
    			}
    			Push(s1,*p);
    			length++;
    			break;
    		case '*':
    		case '/':
    		   for (ch = GetTop(s1); ch != '#'&&ch != '+' && ch != '-'; ch = GetTop(s1))
    		   {
    			   if (ch == '(')
    			   {
    				   break;
    			   }
    			   else
    			   {
    				   Pop(s1,ch);
    				   Push(s2,ch);
    			   }
    		   }
    		   Push(s1,*p);
    		   length++;
    		   break;
    		   //遇操作数则直接压入栈s2中
    		default:
    			Push(s2,*p);
    			length++;
    		}
    	}
    	//若栈s1非空，则将栈中元素依次弹出并压入栈s2中
    	while (!StackEmpty(s1) && GetTop(s1) != '#')
    	{
    		Pop(s1,ch);
    		Push(s2,ch);
    	}
    	//最后将栈s2输出，逆序排列成字符串;
    	char *result;
    	result = (char *)malloc(sizeof(char)*(length+1));
    	result += length;
    	*result = '\0';
    	result--;
    	for (;!StackEmpty(s2); result--)
    	{
    		Pop(s2,ch);
    		*result = ch;
    	}
    	++result;
    	DestroyStack(s1);
    	DestroyStack(s2);
    	return result;
    	
    }
    
    
    int main()
    {
    	char str[10000];
    	scanf("%s",str);
    	printf("%s\n",RPExpression(str));
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关栈应用——逆波兰算法

> 个人主页：[【?个人主页】][Link 1] > 系列专栏：[【❤️数据结构与算法】][Link 2] > 学习名言：传屐朝寻药，分灯夜读书系列文章目录

约定不等于承诺〃/ 2024年04月11日 13:23/ 0 赞/ 65 阅读

相关【队列栈】逆波兰表达式

> 逆波兰表达式(Reverse Polish Notation)，一种不需要括号的后缀表达式。后缀表达式的所有运算符都在数字之后出现。 E.g. 中缀表示式：9

小鱼儿/ 2022年12月02日 15:24/ 0 赞/ 150 阅读

相关 [数据结构]栈实现中缀表达式转换为逆波兰表达式并计算

目录一. 概述 1. 什么是中缀表达式 2.什么是逆波兰表达式 3.为什么需要逆波兰表达式二. 实现原理

迈不过友情╰/ 2022年11月18日 02:27/ 0 赞/ 168 阅读

相关 NOJ数据结构021——逆波兰表达式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

系统管理员/ 2022年10月14日 11:00/ 0 赞/ 177 阅读

相关数据结构栈的应用逆波兰表达式

include <stdio.h> include <stdlib.h> define STACT_INIT_SIZE 100 d

墨蓝/ 2022年09月19日 01:30/ 0 赞/ 155 阅读

相关波兰表达式和逆波兰表达式

波兰表达式和逆波兰表达式分别是一颗二叉树的前序遍历和后序遍历。方法一：递归 \include <iostream> \include <string> using

拼搏现实的明天。/ 2022年08月05日 02:44/ 0 赞/ 185 阅读

相关数据结构逆波兰表达式求值

mystack头文件代码： define MAXSIZE 100 //顺序栈的存储结构 template <class T> str

分手后的思念是犯贱/ 2022年05月23日 12:05/ 0 赞/ 212 阅读

相关【数据结构算法】栈（三）：逆波兰表达式

逆波兰表达式（1-2）（4+5）转换为逆波兰表达式：1 2 - 4 5 + ，这种方式对于计算机来说是容易接受的。只需要利用栈的特点，就可以将这种后缀表达式的性能发挥到

分手后的思念是犯贱/ 2022年05月21日 02:15/ 0 赞/ 201 阅读

相关波兰表达式与逆波兰表达式

文章目录波兰表达式逆波兰表达式波兰表达式计算逆波兰表达式计算总结常见的算术表达式，称为`

墨蓝/ 2022年05月14日 05:12/ 0 赞/ 292 阅读

相关数据结构-栈应用之逆波兰表达式（后缀表达式）

逆波兰表达式含义我就不做赘述了，摘自百科上的一段话：逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。

迈不过友情╰/ 2022年05月12日 13:20/ 0 赞/ 231 阅读