首页 > 代码库 > SDUTOJ 2484 算术表达式的转换（栈）

SDUTOJ 2484 算术表达式的转换（栈）

2024-08-04 16:23:15   216人阅读

算术表达式的转换

Time Limit: 1000MS Memory limit: 65536K

题目描述

小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。
   因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。

输入

 输入一算术表达式，以\‘#\‘字符作为结束标志。（数据保证无空格,只有一组输入）

输出

 输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。

示例输入

a*b+(c-d/e)*f#

示例输出

+*ab*-c/def
a*b+c-d/e*f
ab*cde/-f*+

提示

      只要明白了算术表达式的前缀式，中缀式，后缀式是怎么得到的就可以写出来了，只是用数组模拟栈很麻烦...

来源

 

示例程序



#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

using namespace std;

int bijiao(char ch)
{
    if(ch==‘+‘||ch==‘-‘)
    {
        return 1;
    }
    if(ch==‘*‘||ch==‘/‘)
    {
        return 2;
    }
    if(ch==‘(‘)
    {
        return 3;
    }
}

void qian(char str[])
{
    char a[10100];
    char b[10010];
    char q[11000];
    int pp = 0;
    int k = 0;
    int h = 0;
    int len = strlen(str);
    for(int i=len-2; i>=0; i--)
    {
        a[k++] = str[i];
    }
    a[k] = ‘#‘;
    //a[k] = ‘\0‘;
    for(int i=0; a[i]!=‘#‘; i++)
    {
        if((a[i]>=‘a‘ && a[i]<=‘z‘) || (a[i]>=‘A‘ && a[i] <=‘Z‘))
        {
            b[h++] = a[i];
        }
        else
        {
            if(a[i] == ‘)‘)
            {
                q[++pp] = a[i];
            }
            else if(a[i] == ‘(‘)
            {
                for(; q[pp]!=‘)‘; pp--)
                {
                    b[h++] = q[pp];
                }
                pp--;
            }
            else
            {
                if(bijiao(a[i]) < bijiao(q[pp]))
                {
                    if(q[pp] == ‘)‘)
                    {
                        q[++pp] = a[i];
                    }
                    else
                    {
                        b[h++] = q[pp];
                        q[pp] = a[i];
                    }
                }
                else
                {
                    q[++pp] = a[i];
                }
            }
        }
    }
    while(pp!=0)
    {
        b[h++] = q[pp];
        pp--;
    }
    for(int i=h-1; i>=0; i--)
    {
        printf("%c",b[i]);
    }
    printf("\n");
}

void zhong(char str[])
{
    for(int i=0; str[i]!=‘#‘; i++)
    {
        if(str[i]!=‘(‘ && str[i]!=‘)‘)
        {
            printf("%c",str[i]);
        }
    }
    printf("\n");
}

void hou(char str[])
{
    char qq[100100];
    int p = 0;
    for(int i=0; str[i]!=‘#‘; i++)
    {
        if((str[i]>=‘A‘ && str[i]<=‘Z‘) || (str[i]>=‘a‘ && str[i]<=‘z‘))
        {
            printf("%c",str[i]);
        }
        else
        {
            if(p == 0)
            {
                qq[++p] = str[i];
            }
            else if(str[i] == ‘(‘)
            {
                qq[++p] = str[i];
            }
            else if(str[i] == ‘)‘)
            {
                for(; qq[p]!=‘(‘; p--)
                {
                    printf("%c",qq[p]);
                }
                p--;
            }
            else
            {
                if(bijiao(str[i]) <= bijiao(qq[p]))
                {
                    if(qq[p] == ‘(‘)
                    {
                        qq[++p] = str[i];
                    }
                    else
                    {
                        printf("%c",qq[p]);
                        qq[p] = str[i];
                    }
                }
                else
                {
                    qq[++p] = str[i];
                }
            }
        }
    }
    while(p!=0)
    {
        printf("%c",qq[p]);
        p--;
    }
    printf("\n");
}

int main()
{
    char str[10010];
    while(scanf("%s",str)!=EOF)
    {
        //printf("str = %s\n",str);
        qian(str);
        zhong(str);
        hou(str);
    }
    return 0;
}

SDUTOJ 2484 算术表达式的转换（栈）


联系
我们