考研网 发表于 2018-12-7 17:05:07

2019考研数据结构C语言版详解答案:栈和队列(11)

《数据结构(C语言版)》考试内容两大类:概念,算法。自从计算机专业课统考以后,专业课考试题型分为2类,一类选择题,一类综合应用题。要想把数据结构这门专业课复习好,除了做练习题,还要掌握2019考研计算机数据结构(C语言版)基础知识,只有基础知识掌握牢固,才能在做数据结构算法题目时得心应手。本次新东方在线整理了数据结构C语言版答案详解,各位考生可以对照着题目与答案详解,把计算机专业课的数据结构复习一遍。
    3.21 假设表达式有单字母变量和双目四则运算符构成。试写一个算法,将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。
    解:
    // 输入的表达式串必须为#...#格式
    void InversePolandExpression(char Buffer[])
    {
    Stack s;
    InitStack(s);
    int i=0,j=0;
    ElemType e;
    Push(s,Buffer);
    i++;
    while(Buffer!='#'){
    if(!IsOperator(Buffer)){ // 是操作数
    Buffer=Buffer;
    i++;
    j++;
    }
    else{ // 是操作符
    GetTop(s,e);
    if(Prior(e,Buffer)){// 当栈顶优先权高于当前序列时,退栈
    Pop(s,e);
    Buffer=e;
    j++;
    }
    else{
    Push(s,Buffer);
    i++;
    }
    }
    }
    while(!StackEmpty(s)){
    Pop(s,e);
    Buffer=e;
    j++;
    }
    }
    Status IsOpertor(char c)
    {
    char *p="#+-*/";
    while(*p){
    if(*p==c)
    return TRUE;
    p++;
    }
    return FALSE;
    }
    Status Prior(char c1,char c2)
    {
    char ch[]="#+-*/";
    int i=0,j=0;
    while(ch && ch!=c1) i++;
    if(i==2) i--; // 加和减可认为是同级别的运算符
    if(i==4) i--; // 乘和除可认为是同级别的运算符
    while(ch && ch!=c2) j++;
    if(j==2) j--;
    if(j==4) j--;
    if(i>=j) return TRUE;
    else return FALSE;
    }
    思考题:
    如题3.21的假设条件,试写一个算法,对以逆波兰式表示的表达式求值。
页: [1]
查看完整版本: 2019考研数据结构C语言版详解答案:栈和队列(11)