表达式求值(栈和队列)

表达式求值(栈和队列)

时间: 1ms        内存:1000M

描述:

利用栈来实现含有加,减,乘,除等基本运算,输出表达式的值

输入:

3x(15/5)+8

输出:

17

示例输入:

24-[6+(27/3)x2]

示例输出:

0

提示:

参考答案(内存最优[752]):

#include <stdio.h>
#include <ctype.h>
int youxian(char ch)
{
	switch(ch)
	{
		case '[':
		case '(':  return 1;		
		case ']':
		case ')':  return 2;
		case 'x':  return 3;
		case '/':  return 4;
		default: return 0;
	}
}
void ruzhan(char *str,int a[][2],int *n) 
{
    int i,t;
    *n=1;
    a[0][0]=1;
    a[0][1]='(';
    for (i=0;str[i];)
    {
        if (isdigit(str[i]))
        {
            a[*n][0]=0;
            a[*n][1]=0;
            while (isdigit(str[i]))
            {
                a[*n][1]=a[*n][1]*10+str[i]-'0';
                i++;
            }
        }
        else
        {
			t=youxian(str[i]);
			if(t!=0)
				a[*n][0]=t;
            else
            {
                if (i==0||(!isdigit(str[i-1])&&str[i-1]!=')'))
                {
                    a[*n][0]=0;
                    a[*n][1]=0;
                    (*n)++;
                }
                if (str[i]=='+')
					a[*n][0]=5;
                else
					a[*n][0]=6;
            }
            a[*n][1]=str[i];
            i++;
        }
        (*n)++;
    }
    a[*n][0]=2;
    a[*n][1]=')';
    (*n)++;
}

void poland(int a[][2],int n,int p[][2],int *m)
{
    int i;
    int stack[1000];
    int d=0;
    *m=0;
    for (i=0;i<n;i++)
    {
        if(a[i][0]==0)
			stack[d++]=i;
        else if(a[i][0]==1)
			stack[d++]=i;
        else if(a[i][0]==2)
		{
            while (a[stack[d-1]][0]!=1)
            {
                d--;
                p[*m][0]=a[stack[d]][0];
                p[*m][1]=a[stack[d]][1];
                (*m)++;
            }
            d--;
        }
        else if(a[i][0]==3||a[i][0]==4)
        {
            while (a[stack[d-1]][0]==0||a[stack[d-1]][0]==3||a[stack[d-1]][0]==4)
            {
                d--;
                p[*m][0]=a[stack[d]][0];
                p[*m][1]=a[stack[d]][1];
                (*m)++;
            }
            stack[d++]=i;
        }
        else if(a[i][0]==5||a[i][0]==6)
        {
            while(a[stack[d-1]][0]!=1)
            {
                d--;
                p[*m][0]=a[stack[d]][0];
                p[*m][1]=a[stack[d]][1];
                (*m)++;
            }
            stack[d++]=i;
        }
    }
}
int qiuhe(int p[][2],int m)
{
    int stack[1000];
    int d=0;
    int i;
    for (i=0;i<m;i++)
    {
        if (p[i][0]==0) stack[d++]=p[i][1];
        else
        {
            int a,b;
            b=stack[--d];
            a=stack[--d];
            if (p[i][0]==3) stack[d++]=a*b;
            else if (p[i][0]==4) stack[d++]=a/b;
            else if (p[i][0]==5) stack[d++]=a+b;
            else stack[d++]=a-b;
        }
    }
    return stack[0];
}
int main()
{
    int a[1000][2],p[1000][2];
	int n,m;
	char s[1000];
	gets(s);
	ruzhan(s,a,&n);
    poland(a,n,p,&m);
    printf("%d\n",qiuhe(p,m));
    return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <ctype.h>
int youxian(char ch)
{
	switch(ch)
	{
		case '[':
		case '(':  return 1;		
		case ']':
		case ')':  return 2;
		case 'x':  return 3;
		case '/':  return 4;
		default: return 0;
	}
}
void ruzhan(char *str,int a[][2],int *n) 
{
    int i,t;
    *n=1;
    a[0][0]=1;
    a[0][1]='(';
    for (i=0;str[i];)
    {
        if (isdigit(str[i]))
        {
            a[*n][0]=0;
            a[*n][1]=0;
            while (isdigit(str[i]))
            {
                a[*n][1]=a[*n][1]*10+str[i]-'0';
                i++;
            }
        }
        else
        {
			t=youxian(str[i]);
			if(t!=0)
				a[*n][0]=t;
            else
            {
                if (i==0||(!isdigit(str[i-1])&&str[i-1]!=')'))
                {
                    a[*n][0]=0;
                    a[*n][1]=0;
                    (*n)++;
                }
                if (str[i]=='+')
					a[*n][0]=5;
                else
					a[*n][0]=6;
            }
            a[*n][1]=str[i];
            i++;
        }
        (*n)++;
    }
    a[*n][0]=2;
    a[*n][1]=')';
    (*n)++;
}

void poland(int a[][2],int n,int p[][2],int *m)
{
    int i;
    int stack[1000];
    int d=0;
    *m=0;
    for (i=0;i<n;i++)
    {
        if(a[i][0]==0)
			stack[d++]=i;
        else if(a[i][0]==1)
			stack[d++]=i;
        else if(a[i][0]==2)
		{
            while (a[stack[d-1]][0]!=1)
            {
                d--;
                p[*m][0]=a[stack[d]][0];
                p[*m][1]=a[stack[d]][1];
                (*m)++;
            }
            d--;
        }
        else if(a[i][0]==3||a[i][0]==4)
        {
            while (a[stack[d-1]][0]==0||a[stack[d-1]][0]==3||a[stack[d-1]][0]==4)
            {
                d--;
                p[*m][0]=a[stack[d]][0];
                p[*m][1]=a[stack[d]][1];
                (*m)++;
            }
            stack[d++]=i;
        }
        else if(a[i][0]==5||a[i][0]==6)
        {
            while(a[stack[d-1]][0]!=1)
            {
                d--;
                p[*m][0]=a[stack[d]][0];
                p[*m][1]=a[stack[d]][1];
                (*m)++;
            }
            stack[d++]=i;
        }
    }
}
int qiuhe(int p[][2],int m)
{
    int stack[1000];
    int d=0;
    int i;
    for (i=0;i<m;i++)
    {
        if (p[i][0]==0) stack[d++]=p[i][1];
        else
        {
            int a,b;
            b=stack[--d];
            a=stack[--d];
            if (p[i][0]==3) stack[d++]=a*b;
            else if (p[i][0]==4) stack[d++]=a/b;
            else if (p[i][0]==5) stack[d++]=a+b;
            else stack[d++]=a-b;
        }
    }
    return stack[0];
}
int main()
{
    int a[1000][2],p[1000][2];
	int n,m;
	char s[1000];
	gets(s);
	ruzhan(s,a,&n);
    poland(a,n,p,&m);
    printf("%d\n",qiuhe(p,m));
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞