数据结构——逆波兰表示法

短命女 2022-07-11 13:26 271阅读 0赞

没想到第一次写数据结构就把我折腾死了呀~

我看的是一本AOJ的书，然后以后的算法也是跟着书的目录来~

题目的话会结合TOJ的一起写，可以对照着看哦~

这个逆波兰表示法我就不多讲了，AOJ我用的堆栈。

在这里我们可以运用栈的特点来实现后缀表达式，思路如下：

1.首先当遇到运算操作数时将其进行push操作；

2.当遇到操作符是将此时的栈pop两次，先取出的栈顶为右操作数；

3.执行此方法到整个数组遍历完。

![20170129234142796][]

**AOJ ALDSQ\_1\_3\_A:Stack**

（简单的四则运算，没有()，符号在后，仅一组数据）

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int S[1001],top;
    void push(int x)
    {
    	S[++top]=x;//top加1之后将元素插入top所指的位置 
    }
    int pop()
    {
    	top--;//返回top所指的元素 
    	return S[top+1];
    }
    int main()
    {
    	int a,b;
    	top=0;
    	char s[100];
    	while(scanf("%s",s)!=EOF)
    	{
    		if(s[0]=='+')
    		{
    			a=pop();
    			b=pop();
    			push(a+b);
    		} 
    		else if(s[0]=='-')
    		{
    			a=pop();
    			b=pop();
    			push(a-b);
    		} 
    		else if(s[0]=='*')
    		{
    			a=pop();
    			b=pop();
    			push(a*b);
    		} 
    		else if(s[0]=='/')
    		{
    			a=pop();
    			b=pop();
    			push(a/b);
    		} 
    		else
    		push(atoi(s));//atoi()用来将字符串形式的数字转换为整型数值
    	}
    	printf("%d\n",pop());
    	return 0;
    }

**TOJ 1519**

**描述**

逆波兰表达式是一种把运算符放置的算术表达式，例如普通的表达式2+3的逆波兰表示法+2 3.逆波兰表达式的优点是运算符之间不必有优先级关系，也不用括号，  
例如（2+3）\*4的逆波兰的表达式为\*+2 3 4；本题求解逆波兰表达式的值，其中运算法只有\* + - /.每个数据最多不超过100

**输入**

输入数据有多组，每组一行表达式，其中运算符和运算数之间用空格表示

**输出**

输出结果值，保留六位小数。

**样例输入**

\* + 11.0 12.0 + 24.0 35.0

**样例输出**

1357.000000

用堆栈做的

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<algorithm>
    #include<stack>
    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    int main()
    {
    	int i,j,l;
    	double p,q;
    	char a[1001],b[31],c[30];
    	string d;
    	while(gets(a)!=NULL)
    	{
    		stack<string>f;//建立堆栈
    		l=strlen(a);
    		for(i=0;i<l;i++)
    		{
    			if(a[i]!=' ')
    			{
    				if(a[i]>='0'&&a[i]<='9')
    				{
    					j=0;
    					while(i<l&&a[i]!=' ')
    					{
    						b[j++]=a[i];
    						i++;
    					}
    					b[j]=0;
    					while(1)
    					{
    						d=f.top();
    						for(j=0;j<d.length();j++)
    						c[j]=d[j];
    						c[j]=0;
    						if(c[0]>='0'&&c[0]<='9')
    						{
    							p=atof(b);
    							q=atof(c);
    							f.pop();
    							d=f.top();
    							f.pop();
    							if(d[0]=='+')
    							p+=q;
    							else if(d[0]=='-')
    							p=q-p;
    							else if(d[0]=='*')
    							p*=q;
    							else if(d[0]=='/')
    							p=q/p;
    							b[0]=0;
    							sprintf(b,"%.6f",p);
    							//f.push(b);
    						}
    						else
    						{
    							p=atof(b);
    							sprintf(b,"%.6f",p);
    							f.push(b);
    							break;
    						}
    						if(f.empty())
    						{
    							p=atof(b);
    							sprintf(b,"%.6f",p);
    							f.push(b);
    							break;
    						}
    					}
    				}
    				else
    				{
    					b[0]=a[i];
    					b[1]=0;
    					f.push(b);
    				}
    			}
    		}
    		while(!f.empty())
    		{
    			d=f.top();
    			for(j=0;j<d.length();j++)
    			c[j]=d[j];
    			c[j]=0;
    			f.pop();
    			printf("%s\n",c);
    		}
    		
    	}
    }

然后这是用的dp做。（我感觉更方便了？）

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>//1519
    char s[101];
    int i,n;
    double f()
    {
    	int j,k;
    	double l;
    	char a[10];
    	memset(a,0,sizeof(a));
    	for(j=i,k=0;j<n;j++,k++)
    	if(s[j]!=' ')a[k]=s[j];
    	else if(s[j]==' '&&a[j+1]!=' ')break;
    	i=j+1;	
    	switch(a[0])
    	{
    		case'+':return f()+f();
        		case'-':return f()-f();
        		case'*':return f()*f();
        		case'/':return f()/f();
        		default: return atof(a); //把字符串转换成浮点数名字
        	}
    }
    int main()
    {
        double sum;
        while(gets(s)!=NULL)
        {
        	 i=0;
        	 n=strlen(s);
        	 sum=f();
        	 printf("%f\n",sum);
        }
    }

[20170129234142796]: /images/20220711/45e0f01d28394d15931173eddae960e8.png