ch03.表栈队列--中缀转后缀的栈实现

╰+攻爆jí腚メ 2023-02-21 06:53 83阅读 0赞

### ch03.表栈队列--中缀转后缀的栈实现 ###

*   *  0.引言
     *  1.使用栈实现
     *  2.参考实现

## 0.引言 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ_size_16_color_FFFFFF_t_70 1][]

我的实现流程：  
1.左括号或栈空，直接入栈;  
2.栈顶运算优先级大于该运算符,则出栈;  
3.栈顶运算符优先级小于该运算符,则入栈；  
4.‘）’单独处理.

## 1.使用栈实现 ##

#include <iostream>
    #include <algorithm>
    #include <fstream>
    #include <stdlib.h>
    #include <assert.h>
    #include <string.h>
    using namespace std;
    
    
    #define  EmptyTOS -1
    #define  MinStackSize  5
    
    
    #define ElementType char
    //栈的数组实现
    struct StackRecord;
    typedef struct StackRecord  *Stack;
    
    struct StackRecord
    {
        
    	int Capacity;
    	int TopOfStack;
    	ElementType *Array;
    };
    
    void MakeEmpty(Stack s)
    {
        
    	s->TopOfStack = EmptyTOS;
    }
    
    void CreateStack(Stack *s,int MaxElements)
    {
        
    	Stack tmp;
    	if (MaxElements < MinStackSize)
    		cout << "Error! Stack is too small!" << endl;
    
    	tmp = (Stack)malloc(sizeof(struct StackRecord));
    
    	if (tmp == NULL)
    		cout << "Error! out of space!" << endl;
    
    	(tmp)->Array = (ElementType*)malloc(sizeof(ElementType)*MaxElements);
    
    	if ((tmp)->Array == NULL)
    		cout << "Error! out of space!" << endl;
    
    	(tmp)->Capacity = MaxElements;
    	MakeEmpty(tmp);
    	*s = tmp;
    }
    
    int IsEmpty(Stack *s)
    {
        
    	return (*s)->TopOfStack == EmptyTOS;
    }
    
    void Push(ElementType x, Stack *s)
    {
        
    	(*s)->Array[++(*s)->TopOfStack] = x;
    	//s->TopOfStack++;
    }
    
    ElementType	 TopAndPop(Stack *s)
    {
        
    	if (!IsEmpty(s))
    		return (*s)->Array[(*s)->TopOfStack--];//先弹出再自减
    	cout << "Error!Empty Stack!" << endl;
    	return 0;
    }
    
    void Pop(Stack *s)
    {
        
    	if (IsEmpty(s)) cout << "Error! Empty Stack!" << endl;
    	else
    		(*s)->TopOfStack--;
    }
    
    ElementType LookTopElement(Stack *s)
    {
        
    	if (!IsEmpty(s))
    		return (*s)->Array[(*s)->TopOfStack];//先弹出再自减
    	cout << "Error!Empty Stack!" << endl;
    	return 0;
    }
    ///中缀转后缀
    int JudgePriority(char src)
    {
        
    	switch (src)
    	{
        
    	//case '(':return 6;
    	case '*':return 5;
    	case '+':return 4;
    	case ')':return 3;
    	case '(':return 2;
    	default:
    		break;
    	}
    }
    
    bool IsNum(char *str)
    {
        
    	if ((*str >= '0' && *str <= '9') || *str == '.')
    		return true;
    	return false;
    }
    
    void PushOrPop(char* src, Stack *stack,char *output)
    {
        
    
    	if (JudgePriority(*src)==2 || IsEmpty(stack))//1.左括号或栈空，直接入栈
    	{
        
    		Push(*src, stack);
    	}
    	if (JudgePriority(*src) < JudgePriority(LookTopElement(stack)) && JudgePriority(*src)!=2 && JudgePriority(*src) != 3)
    	{
        
    		while (JudgePriority(*src) <= JudgePriority(LookTopElement(stack)))//2.栈顶运算优先级大于该运算符,则出栈
    		{
        
    			*output = TopAndPop(stack);
    			output++;
    		}
    		Push(*src, stack);//出栈后再将src入栈
    		//return output;//地址传出去
    	}
    
    	if (JudgePriority(*src) > JudgePriority(LookTopElement(stack)))//3.栈顶运算符优先级小于该运算符,则入栈
    	{
        
    		Push(*src, stack);
    	}
    	if (JudgePriority(*src) == 3)//4.‘）’
    	{
        
    		while (JudgePriority(LookTopElement(stack))!=2)//不是'('就一直出栈
    		{
        
    			*output = TopAndPop(stack);
    			output++;
    		}
    		Pop(stack);//直接丢掉'('
    		//return output;//地址传出去
    	}
    }
    
    
    void Infix2Postfix(Stack *stack,  char *src, char *output)
    {
        
    	double tmp0 = 0.0; 
    	while (*src != '\0')
    	{
        
    		char tmp[6] = "00000";
    		if (IsNum(src))
    		{
        
    			//tmp0 = Char2Num(src);
    			*output = *src;
    			src++;
    			output++;
    		}
    		else
    		{
        
    			PushOrPop(src,stack, tmp);//这里指针老师传不出来值，只能重新定义一个变量tmp
    			for (int i = 0;i<6;i++)
    			{
        
    				if(tmp[i]!='0')
    				{
        
    					*output = tmp[i];
    					output++;
    				}
    				else
    				{
        
    					break;
    				}
    			}
    			//free(tmp);
    			src++;
    		}
    	}
    	while(!IsEmpty(stack))//最后再判断是否为空
    	{
        
    		//while (output != '\0') output++;
    		*output = TopAndPop(stack);
    		output++;
    	}
    }
    
    void Infix2PostfixTest()
    {
        
    	char Source1[] = "1+2*3+(4*5+6)*7";
    	char Output[] = "0000000000000000";
    
    	int N = sizeof(Output) / sizeof(char);
    	Stack st1;
    
    	CreateStack(&st1, MaxElement);
    	Infix2Postfix(&st1, Source1, Output);
    
    	for (int i = 0; i < N; i++)
    	{
        
    		if (Output[i] != '0')
    		{
        
    			cout << Output[i];
    		}
    		else
    		{
        
    			break;
    		}
    	}
    	cout << endl;
    }
    
    
    int main(int argc, char **argv)
    {
        
    	//SymbolPairsTest();
    	//PostFixTest();
    	Infix2PostfixTest();
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20200629172242980.png_pic_center]

这个代码真丑!

## 2.参考实现 ##

*  [方法参考][Link 1]

思考了一下，思路很简单，但是实现起来比栈的实现更复杂一点，略。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629171636888.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200629171840546.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ==,size_16,color_FFFFFF,t_70
[20200629172242980.png_pic_center]: https://img-blog.csdnimg.cn/20200629172242980.png#pic_center
[Link 1]: https://blog.csdn.net/qq_29462849/article/details/93649198