欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

浙大版《数据结构(第2版)》题目集-习题3.11 表达式转换 (25分)

程序员文章站 2022-06-10 19:19:01
...

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。

输出格式:

在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +

参考代码:

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

typedef struct snode *stack;
struct snode{
    char ch[20];
    int top;
};

stack CreateStack(); //创建堆栈
void push(stack s,char c); //入栈
char pop(stack s); //出栈

int main()
{
    char ch1[150]; //用来存储符号优先级
    ch1['(']=0;
    ch1['+']=1;
    ch1['-']=1;
    ch1['*']=2;
    ch1['/']=2;
    char s[21]; //用来存储中缀表达式
    scanf("%s",s);
    int l=strlen(s);
    stack st=CreateStack();
    int flag=0; //该标志位用来控制格式输出
    for(int i=0;i<l;i++) //遍历中缀表达式符号
    {
        if(s[i]=='(')
        {
            push(st,s[i]);
        }
        else if(s[i]==')')
        {
            char t;
            t=pop(st);
            while(t!='(')
            {
                printf(" %c",t);
                t=pop(st);
            }
            flag=1;
        }
        else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')
        {
            if(s[i]=='+'&&(s[i-1]=='('||i==0));//如果这个+表示正号,不进行操作
            else if(s[i]=='-'&&(s[i-1]=='('||i==0))//如果这个-表示负号,直接输出
            {
                printf("-");
            }
            else if(ch1[s[i]]>ch1[st->ch[st->top]]||st->top==-1)
            {
                push(st,s[i]);
                flag=1;
            }
            else
            {
                printf(" %c",pop(st));
                while(ch1[s[i]]<=ch1[st->ch[st->top]]&&st->top!=-1)
                {
                    printf(" %c",pop(st));
                }
                push(st,s[i]);
                flag=1;
            }
        }
        else //运算数直接输出(包含小数.)
        {
            if(flag)
            {
                printf(" ");
                flag=0;
            }
            printf("%c",s[i]);
        }
    }
    while(st->top!=-1)//输出堆栈中剩余的符号
    {
        printf(" %c",pop(st));
    }
    return 0;
}

stack CreateStack()
{
    stack s=(stack)malloc(sizeof(struct snode));
    s->top=-1;
    return s;
}

void push(stack s,char c)
{
    (s->top)++;
    s->ch[s->top]=c;
}

char pop(stack s)
{
    return s->ch[(s->top)--];
}

思路:

这题代码我是参考中国大学MOOC.数据结构(浙江大学)[1] 中所讲解的思路去写的,但是在一些细节处理上会更具体些,细节方面可以看代码注释,这里附上课程PPT的思路截图。
浙大版《数据结构(第2版)》题目集-习题3.11 表达式转换 (25分)
浙大版《数据结构(第2版)》题目集-习题3.11 表达式转换 (25分)

刚开始按照该思路写时,有个别测试点不通过的情况,后来参考博主damon-lin[2] 文章中的测试样例通过所有测试点,附上测试案例供参考。

序号 输入 输出
1 2+3*(7-4)+8/4 2 3 7 4 - * + 8 4 / +
2 ((2+3)*4-(8+2))/5 2 3 + 4 * 8 2 + - 5 /
3 1314+25.5*12 1314 25.5 12 * +
4 -2*(+3) -2 3 *
5 123 123

参考资料

[1]中国大学MOOC.数据结构(浙江大学): https://www.icourse163.org/learn/ZJU-93001?tid=1450069451#/learn/announce
[2]damon-lin: https://blog.csdn.net/linsheng9731/article/details/22619447

相关标签: C语言编程