线性表_栈_逆波兰计算式（Reverse Polish Notation）

我不是女神ヾ 2022-06-16 06:10 139阅读 0赞

**1.概念**

逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）

实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中序表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

新建一个表达式,如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。图示如下：

![20170507224802890][]

**2.代码**

/*
    *RPN:Reverse Polish Notation
    *逆波兰表达式：将数据存储在栈中进行计算时，入栈时将按照以下顺序
    *如：（1-2）*（4+5） RPN是： 1 2 - 4 5 + *
    *如： 5 -（6+7）* 8 + 9 / 4  RPN是：  5 6 7 + 8 * - 9 4 / 
    */
    
    #include <stdio.h>
    #include <ctype.h>
    #include <stdlib.h>
    
    #define STACK_INIT_SIZE 20
    #define STACKINCREMENT  10
    #define MAXBUFFER       10
    
    typedef double ElemType;
    typedef struct
    {
    	ElemType *base;
    	ElemType *top;
    	int stacksize;
    }sqStack;
    
    //初始化栈
    InitStack(sqStack  *s)
    {
    	s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    	if (!s->base) exit(0);
    	s->top = s->base;
    	s->stacksize = STACK_INIT_SIZE;
    }
    
    //入栈操作
    Push(sqStack  *s, ElemType e)
    {
    	if (s->top - s->base >= s->stacksize)
    	{
    		s->base = (ElemType *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(ElemType));
    		if (!s->base) exit(0);
    		s->top = s->base + s->stacksize;
    	}
    
    	*(s->top) = e;
    	s->top++;
    }
    
    //出栈操作
    Pop(sqStack  *s, ElemType *e)
    {
    	if (s->top == s->base) return;
    	*e = *--(s->top);
    }
    
    //获取栈长度
    int StackLen(sqStack s)
    {
    	return (s.top - s.base);
    }
    
    int main()
    {
    	sqStack s;
    	char c;
    	double d, e;
    	char str[MAXBUFFER];
    	int i = 0;
    	InitStack(&s);
    
    	printf("Input datas with Reverse Polish Notation,Ending with '#' \n");
    	scanf("%c", &c);
    
    	while (c != '#')
    	{
    		while (isdigit(c))  //数字与空格的处理
    		{
    			str[i++] = c;
    			str[i] = '\0';
    			if (i >= 10)
    			{
    				printf("ERROR:Data is out of range \n");
    				return -1;
    			}
    			scanf("%c", &c);
    			if (c == ' ')
    			{
    				d = atof(str);
    				Push(&s, d);
    				i = 0;
    				break; 
    			}
    		}
    		switch (c)        //四则运算符号处理
    		{
    		case '+':
    			Pop(&s, &e);
    			Pop(&s, &d);
    			Push(&s, d + e);
    			break;
    		case '-':
    			Pop(&s, &e);
    			Pop(&s, &d);
    			Push(&s, d - e);
    			break;
    		case '*':
    			Pop(&s, &e);
    			Pop(&s, &d);
    			Push(&s, d * e);
    			break;
    		case '/':
    			Pop(&s, &e);
    			Pop(&s, &d);
    			if (e != 0)
    			{
    				Push(&s, d / e);
    			}
    			else
    			{
    				printf("ERROR:Input Wrong");
    				return -1;
    			}
    			break;
    		}
    		scanf("%c", &c);
    	}
    	Pop(&s, &d);
    	printf("Result is: %f\n", d);
    
    	return 0;
    }

**3.运行结果**

5 -（6+7）\* 8 + 9 / 4 RPN是： 5 6 7 + 8 \* - 9 4 /

**![20170507224540390][]**

[20170507224802890]: /images/20220616/80570a81414a4e4289dda1869f60118c.png
[20170507224540390]: /images/20220616/3ce34f3597284e97bf0d7efdc01ec9a1.png