ch03.表栈队列--后缀表达式的栈实现

╰+哭是因爲堅強的太久メ 2023-02-21 06:21 18阅读 0赞

### ch03.表栈队列--后缀表达式的栈实现 ###

*   *  0.引言
     *  1.使用栈实现

## 0.引言 ##

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

## 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 double
    /*************************栈的数组实现*********/
    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;
    }
    
    /*************************后缀表达式*********/
    const int MaxElement = 100;
    bool IsNum(char *str)
    {
        
    	if ((*str >= '0' && *str <= '9') || *str == '.')
    		return true;
    	return false;
    }
    
    double Char2Num(char *str)
    {
        
    	double n = 0.0;
    	double tmp = 10.0;
    	int flag = 0;
    	assert(str);
    		if(*str >= '0' && *str <= '9')
    		{
        
    			n = n * 10 + (*str - '0');
    			str++;
    		}
    		else if (*str == '.')
    		{
        
    			str++;
    			while (*str >= '0' && *str <= '9')
    			{
        
    				n = n + (*str - '0') / tmp;;
    				tmp = tmp * 10;
    				str++;
    			}
    		}
    		return n;
    }
    
    double Operation(char *src,Stack *stack)
    {
        
    	double tmp1 = 0.0, tmp2 = 0.0;
    	tmp1 = TopAndPop(stack);
    	tmp2 = TopAndPop(stack);
    
    	switch (*src)
    	{
        
    	case '+':return tmp1 + tmp2;
    	case '-':return tmp1 - tmp2;
    	case '*':return tmp1 * tmp2;
    	case '/':return tmp1 / tmp2;
    	default:
    		break;
    	}
    }
    
    void PostFix(char *src,Stack *stack)
    {
        
    	double tmp0 = 0.0;
    	while (*src != '\0')
    	{
        
    		if (IsNum(src))
    		{
        
    			tmp0 = Char2Num(src);
    			Push(tmp0, stack);
    			src++;
    		}
    		else
    		{
        
    			tmp0 = Operation(src, stack);
    			Push(tmp0, stack);
    			src++;
    		}		
    	}
    }
    
    
    void PostFixTest()
    {
        
    	char Source1[] = "6523+8*+3+*";
    	Stack stack;
    
    	CreateStack(&stack, MaxElement);
    	PostFix(Source1,&stack);
    
    	cout << "result:" << endl;
    	while (!IsEmpty(stack))
    	{
        
    		cout << TopAndPop(&stack) << " ";
    	}
    	cout << endl;
    }
    
    
    int main(int argc, char **argv)
    {
        
    	//SymbolPairsTest();
    	PostFixTest();
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20200629100119497.png_pic_center]  
只是实现了最简单的模式，对负数和小数还需更改。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200629095826255.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZiXzk0MTIxOQ==,size_16,color_FFFFFF,t_70#pic_center
[20200629100119497.png_pic_center]: https://img-blog.csdnimg.cn/20200629100119497.png#pic_center