3606 - 中缀表达式求值

3*(2+5)@

21

Hint

用中缀表达式直接求值。

Solution C

#include<stdio.h>
#include<math.h>
#define maxn 101
int push1(int n,double *p,double v)
{
	n++;
	p[n]=v;
	return n;
}
double pop1(int n,double *p)
{
	return p[n];
}
int push2(int n,char *p,char v)
{
	n++;
	p[n]=v;
	return n;
}
int main()
{
	char str[maxn],stackope[maxn],op;
	int nn=0,np=0,i;
	double stacknum[maxn],sec,fir;
	scanf("%s",str);
	for(i=0;str[i]!='@';i++)
	{
		if(str[i]>='0'&&str[i]<='9')
		nn=push1(nn,stacknum,(str[i]-'0')*1.00);
		else
		{
		   if(np==0) np=push2(np,stackope,str[i]);
		  else if(str[i]=='(') np=push2(np,stackope,str[i]);
		  else if(str[i]==stackope[np]) 
		   {
		   	 sec=pop1(nn,stacknum);nn--;
		   	 fir=pop1(nn,stacknum);nn--;
		   	 if(str[i]=='+') { nn=push1(nn,stacknum,fir+sec);}
		   	 if(str[i]=='-') { nn=push1(nn,stacknum,fir-sec);}
		   	 if(str[i]=='*') { nn=push1(nn,stacknum,fir*sec);}
		   	 if(str[i]=='/') { nn=push1(nn,stacknum,fir/sec);}
		   	}
		   	else if(str[i]=='+')
		   	{
		   		if(stackope[np]=='*') 
		   		{
		   		  sec=pop1(nn,stacknum);nn--;
		   	      fir=pop1(nn,stacknum);nn--;
		   	      nn=push1(nn,stacknum,fir*sec);np--;
		   	      np=push2(np,stackope,str[i]);
			    }
			    else if(stackope[np]=='/') 
		   		{
		   		  sec=pop1(nn,stacknum);nn--;
		   	      fir=pop1(nn,stacknum);nn--;
		   	      nn=push1(nn,stacknum,fir/sec);np--;
		   	      np=push2(np,stackope,str[i]);
			    }
			     else if(stackope[np]=='-') 
		   		{
		   		  sec=pop1(nn,stacknum);nn--;
		   	      fir=pop1(nn,stacknum);nn--;
		   	      nn=push1(nn,stacknum,fir-sec);np--;
		   	      np=push2(np,stackope,str[i]);
			    }
			    else
			      np=push2(np,stackope,str[i]);
		   		
		   	 }
		   	 else if(str[i]=='-')
		   	{
		   		if(stackope[np]=='*') 
		   		{
		   		  sec=pop1(nn,stacknum);nn--;
		   	      fir=pop1(nn,stacknum);nn--;
		   	      nn=push1(nn,stacknum,fir*sec);np--;
		   	      np=push2(np,stackope,str[i]);
			    }
			    else if(stackope[np]=='/') 
		   		{
		   		  sec=pop1(nn,stacknum);nn--;
		   	      fir=pop1(nn,stacknum);nn--;
		   	      nn=push1(nn,stacknum,fir/sec);np--;
		   	      np=push2(np,stackope,str[i]);
			    }
			     else if(stackope[np]=='+') 
		   		{
		   		  sec=pop1(nn,stacknum);nn--;
		   	      fir=pop1(nn,stacknum);nn--;
		   	      nn=push1(nn,stacknum,fir+sec);np--;
		   	      np=push2(np,stackope,str[i]);
			    }
		   		else
		   		  np=push2(np,stackope,str[i]);
		   	}
		   	else if(str[i]=='*'||str[i]=='/')
		   	{
		   		if(stackope[np]=='*') 
		   		{
		   		  sec=pop1(nn,stacknum);nn--;
		   	      fir=pop1(nn,stacknum);nn--;
		   	      nn=push1(nn,stacknum,fir*sec);np--;
		   	      np=push2(np,stackope,str[i]);
			    }
			    else if(stackope[np]=='/') 
		   		{
		   		  sec=pop1(nn,stacknum);nn--;
		   	      fir=pop1(nn,stacknum);nn--;
		   	      nn=push1(nn,stacknum,fir/sec);np--;
		   	      np=push2(np,stackope,str[i]);
			    }
			    else
			      np=push2(np,stackope,str[i]); 
                		   		
		   	}
		   	else if(str[i]=='^')
		   	 {
		   	   sec=pop1(nn,stacknum);nn--;
		   	   nn=push1(nn,stacknum,pow(sec,(str[i+1]-'0')));
		   	   i=i+1;
		   	   continue;
		   	}
		   	else
		   	  {
		   	  	while(stackope[np]!='(')
		   	  	{
		   	  	  sec=pop1(nn,stacknum);nn--;
		   	      fir=pop1(nn,stacknum);nn--;
		   	      op=stackope[np];
		   	      if(op=='+') nn=push1(nn,stacknum,fir+sec);
		   	      if(op=='-') nn=push1(nn,stacknum,fir-sec);
		   	      if(op=='*') nn=push1(nn,stacknum,fir*sec);
		   	      if(op=='/') nn=push1(nn,stacknum,fir/sec);
		   	      np--;
		   	  	}
		   	  	np--;
		   	  }
		   }
		    
		}
		while(np!=0)
		{
		 sec=pop1(nn,stacknum);nn--;
	     fir=pop1(nn,stacknum);nn--;
		  op=stackope[np];
  	      if(op=='+') nn=push1(nn,stacknum,fir+sec);
	      if(op=='-') nn=push1(nn,stacknum,fir-sec);
		  if(op=='*') nn=push1(nn,stacknum,fir*sec);
		  if(op=='/') nn=push1(nn,stacknum,fir/sec);
		   	np--;
		}
		printf("%d",(int)stacknum[nn]);
		
	
	return 0;
}

Solution C++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<string>

using namespace std;

int a[101],i=0,p=1;
char sy[101],t[256];
string s;

void push()
{
	sy[++p]=s[i];
}

void pop()
{
	switch(sy[p--])
	{
		case '+':
			a[p]+=a[p+1];
			break;
		case '-':
			a[p]-=a[p+1];
			break;
		case '*':
			a[p]*=a[p+1];
			break;
		case '/':
			a[p]/=a[p+1];
			break;
	}
}
bool can()
{
	if((s[i]=='+'||s[i]=='-')&&sy[p]!='(') return 1;
	if((s[i]=='*'||s[i]=='/')&&(sy[p]=='*'||sy[p]=='/')) return 1;
	return 0;
}

int main()
{
	cin>>s;
	s[s.length()-1]=')';
	sy[p]='(';
	while(i<s.length())
	{
		while(s[i]=='(')
		{
			push();
			i++;
		}
		int x=0;
		while(s[i]>='0'&&s[i]<='9')
			x=x*10+s[i++]-'0';
		a[p]=x;
		do
		{
			if(s[i]==')')
			{
				while(sy[p]!='(')
					pop();
				a[--p]=a[p+1];
			}
			else
			{
				while(can())
					pop();
				push();
			}
			i++;
		}while(i<s.length()&&s[i-1]==')');
	}
	cout<<a[0];
	return 0;
}