精华内容
下载资源
问答
  • C++程序,将后缀表达式用栈转换为前缀表达式
  • 接着说 中缀表达式 转 前缀表达式 原理相同 中缀表达式: (6+3*(7-4))-8/2 1.直接转换法 确定表达式的运算方式, 加括号, 给每一次能运算的都加上: (6+(3*(7-4)))-8/2 (6+(3*(7-4)))-(8/2) ((6+(3*(7-4)))-(8/2)) ...

    上一篇文章讲述了 中缀表达式 转成 后缀表达式

    接着说 中缀表达式 转 前缀表达式

    原理相同
    中缀表达式: (6+3*(7-4))-8/2

    1.直接转换法
      1. 确定表达式的运算方式, 加括号, 给每一次能运算的都加上:
        • (6+(3*(7-4)))-8/2
        • (6+(3*(7-4)))-(8/2)
        • ((6+(3*(7-4)))-(8/2))
      1. 从最里面的一层括号开始运算,转换成后缀表达式的方法为:(忽略括号)符号在前,数字在后
        • (7-4) => -74
        • (3*(7-4)) => (3*(-74)) => *3-74 (把-74看成一个整体)
        • (6+(3*(7-4))) => (6+ (*3-74 )) => +6 3-74 (把3-74看成一个整体)
        • (8/2) => /82
        • ((6+(3*(7-4)))-(8/2)) => (+6 *3-74 ) - ( /82 ) => - +6 *3-74 /82 (把(+6 *3-74 ) 和 ( /82)) 看成一个整体
        前缀表达式: - +6 *3-74 /82
    2.利用栈
    以下来自百度百科:
    • (1) 首先构造一个运算符栈(也可放置括号),运算符(以括号为分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。
    • (2)从右至左扫描中缀表达式,从右边第一个字符开始判断:
      如果当前字符是数字,则分析到数字串的结尾并将数字串直接输出。
      如果是运算符,则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),则将运算符直接入栈;否则将栈顶运算符出栈并输出,直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),再将当前运算符入栈。
      如果是括号,则根据括号的方向进行处理。如果是向右的括号,则直接入栈;否则,遇向左的括号前将所有的运算符全部出栈并输出,遇右括号后将向左、向右的两括号一起出栈(并不输出)。
    • (3) 重复上述操作(2)直至扫描结束,将栈内剩余运算符全部出栈并输出,再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。
      – 如果表达式结束,但栈中还有元素,将所有元素出栈,添加到前缀表达式中

    可能👀看文字有点晕, 直接上图

    中缀表达式: (6+3*(7-4))-8/2

      1. 首先分配2个栈
        在这里插入图片描述
      1. 取字符
        • 2 运算符 直接入 s2; / 操作符 入 s1;
        • 8运算符 入 s2;
        • ’ -'操作符 入 s1; 栈顶元素 / 优先级大于 - 所以取出/ 入s2

    在这里插入图片描述

       - )操作符 入 s1; 
       -  )操作符 入 s1;
       -  4 运算符 入 s2; 
       - '- 操作符 入 s1;
       -  7运算符 入 s2; 
    

    在这里插入图片描述

    • (操作符 将- 放入 s2 中, 移除 ( ) 两个;在这里插入图片描述

    • *操作符 入 s1;

    • 3 运算符 入 s2;

    • '+ 操作符 , 入s1, 但是 栈顶* 优先级大于 + 所以 * 出栈 入 s2
      在这里插入图片描述

    • 6 运算符 入 s2;
      在这里插入图片描述

    • ( 取出 + 作废 ) ( ;
      在这里插入图片描述

    • 结束 依次取出s1

    在这里插入图片描述
    逆缀 输出 - + 6 * 3-74/82

    展开全文
  • 前缀表达式的基本形式是:“运算符号(空格)子前缀表达式(空格)子前缀表达式”,其中“子前缀表达式”可能是一个包含运算符号的前缀表达式,也可能只是一个单纯的运算数。例如:前缀表达式“+ + 2 * 3 – 7 4 / 8...
  • 但是那篇博客没有介绍如何根据前缀表达式计算结果,这里我说一下 定义一个栈,从右向左扫描前缀表达式 如果是操作数,则将操作数压入栈中 如果是运算符,则从栈中取出来两个操作数,计算结果,再放回栈中 下面我们...

    相关原理
    理论部分请参照上面的博客,写的很清楚。

    好的我们来看代码

    举个栗子

    (9-((1+3)*2))/2
    结果是0.5

    def infix_to_prefix(expression):
        assert type(expression)==list
        expression.reverse()
        priority={'+':0,'-':0,'*':1,'/':1}
        operator_list=[]#运算符的英文是operator
        operand_list=[]#操作数的英文是operand
        for each_element in expression:
            if each_element not in priority and each_element not in ['(',')']:
                operand_list.append(each_element)#操作数直接push到操作数栈
            else:
                if each_element not in ['(',')']:
                    #表明此时是运算符,不是括号
                    if len(operator_list)==0 or operator_list[-1]==')':
                        #如果运算符栈为空,或者栈顶元素是右括号,那么直接push
                        operator_list.append(each_element)
                    elif priority[each_element]>=priority[operator_list[-1]]:
                        #如果这个运算符的优先级大于栈顶运算符的优先级,直接push
                        operator_list.append(each_element)
                    else:
                        #此时需要将运算符栈顶的运算符弹出来放到操作数栈中
                        operand_list.append(operator_list.pop())
                else:
                    #此时是括号
                    if each_element==')':
                        #右括号直接入栈
                        operator_list.append(each_element)
                    else:
                        assert each_element=='('
                        #左括号的时候从运算符栈中弹出运算符,直到遇到右括号为止,将这对括号中间的运算符放到操作数栈中
                        while(operator_list[-1]!=')'):
                            operand_list.append(operator_list.pop())
                        operator_list.pop()
        while(len(operator_list)!=0):
            operand_list.append(operator_list.pop())
        operand_list.reverse()           
        return operand_list
    

    在这里插入图片描述

    上面的函数已经将中缀表达式转化为了前缀表达式,相关原理那篇博文已经说的很清楚了。

    但是那篇博客没有介绍如何根据前缀表达式计算结果,这里我说一下

    • 定义一个栈,从右向左扫描前缀表达式
    • 如果是操作数,则将操作数压入栈中
    • 如果是运算符,则从栈中取出来两个操作数,计算结果,再放回栈中

    下面我们根据前缀表达式计算结果

    def compute_prefix_expression(prefix):
        stack=list()
        for i in range(len(prefix)-1,-1,-1):
            element=prefix[i]
            if element not in ['+','-','*','/']:
                stack.append(element)
            else:
                a=stack.pop()
                b=stack.pop()
                stack.append(str(eval(a+element+b)))
        assert len(stack)==1
        return eval(stack[0])
    

    结果:
    在这里插入图片描述

    展开全文
  • 中缀表达式、前缀表达式、后缀表达式


    1 三种算术表达式

    算术表达式由三个部分组成:操作数、运算符、界限符。界限符是必不可少的,也就是括号。括号或者说界限符反映了计算或者说运算符作用的先后顺序。但是有一个波兰数学家想这样做:可以不用界限符也能无歧义地表达运算顺序。于是发明了:① 逆波兰表达式,即后缀表达式;② 波兰表达式,即前缀表达式。

    类型规则例1例2
    中缀表达式运算符在两个操作数中间a+ba+b-c
    后缀表达式运算符在两个操作数后面ab+ab+c-
    前缀表达式运算符在两个操作数前面+ab-+abc

    2 后缀表达式相关考点

    2.1 中缀表达式转后缀表达式

    2.1.1 手算

    中缀转后缀的手算步骤:

    ① 确定中缀表达式中各个运算符的运算顺序,但是有时候运算顺序不唯一,因此对应的后缀表达式也不唯一。为了保证手算和机算结果相同,且保证运算顺序唯一,请遵从“左优先”原则:只要左边的运算符能先计算,就优先算左边的。确定完运算符的运算顺序后,如果有界限符即括号,就可以去掉全部的括号了,或者说可以忽略括号的存在继续下面步骤;

    ② 选择下一个运算符,按照【左操作数 右操作数 运算符】的方式组合成一个新的式子,然后放在原来操作符的位置。如果还有运算符没被处理,就继续②,否则最后得到的式子就是最终结果。下面是一个示例:

    转换前的中缀表达式转换后的后缀表达式
    ((15/(7-(1+1)))*3)-(2+(1+1))15 7 1 1 + - / 3 * 2 1 1 + + -
    2+(3+4)*52 3 4 + 5 * +
    16+2*30/416 2 30 * 4 / +

    2.1.2 机算

    实现中缀表达式转后缀表达式的逻辑过程:初始化一个栈,用于保存暂时还不能确定运算顺序的运算符。从左到右扫描中缀表达式的各个字符,直到末尾。在扫描时可能遇到三种情况:

    ① 当前字符是数字:直接加入后缀表达式,然后处理下一个字符;

    ② 当前字符是括号,又分为两种情况:

    • 1)当前字符是左括号即(则直接将当前字符入栈,然后处理下一个字符;
    • 2)当前字符是右括号即):若栈空则直接处理下一个字符。若栈非空则不断弹出栈顶元素——若弹出左括号(后则停止继续弹出(注意这个左括号(不加入后缀表达式)并直接处理下一个字符,否则将栈顶元素加入后缀表达式,然后继续弹出栈顶元素;

    ③ 当前字符是运算符,又分为两种情况:

    • 1)栈空则直接把当前字符入栈,然后处理下一个字符;
    • 2)栈非空则不断弹出栈顶元素:若栈顶元素是左括号(或优先级低于当前字符的运算符则停止栈顶元素的弹出,再将栈顶元素再次入栈,之后再把当前字符入栈,然后处理下一个字符。若栈顶元素是运算符且优先级高于或等于当前字符,则将栈顶元素加入后缀表达式,然后继续弹出栈顶元素;

    按上述方法处理完所有字符后,若栈非空则将栈中剩余字符依次弹出并依次加入后缀表达式。最后得到的表达式就是最终结果。示例代码如下:

    //本程序只能处理有关运算符+、-、*、/的中缀表达式,不能是÷或者×及其他运算
    //界限符只能是英文状态的左右括号即'('、')',操作数只能是整数
    //本程序不会检查输入的中缀表达式是否正确,因此请您核验好自己的式子是否正确
    #include<stdio.h>
    #include<string.h> //strlen的头文件,用于判断字符串长度
    #include<stdlib.h> //malloc、free的头文件
    #define size 50//假定要转换的中缀表达式的字符数在50个以内
    typedef struct Linknode{ //定义链栈及结点
        char data; //数据域
        struct Linknode *next; //指针域
    }*LiStack;
    bool InitStack(LiStack &S){ //链栈的初始化,不带头结点
        S=NULL; //刚开始没有结点
        return true;
    }
    bool StackEmpty(LiStack S){ //判断栈空
        return S==NULL;
    }
    bool Push(LiStack &S,char x){ //将元素x入栈
        Linknode *s=(Linknode *)malloc(sizeof(Linknode)); //创建新结点
        if(s==NULL) //内存不足,创建失败
            return false;
        s->data=x;
        s->next=S; //将结点s作为链栈的栈顶结点
        S=s; //栈顶指针S指向结点s
        return true;
    }
    bool Pop(LiStack &S,char &x){ //栈顶元素出栈,将值赋给x
        if(S==NULL)
            return false; //栈空则返回NULL
        x=S->data;
        Linknode *p=S;
        S=S->next;
        free(p);
        return true;
    }
    int main(){
        char temp,a[size],b[size]; //静态数组a、b分别存放要转换的中缀表达式和转换后的后缀表达式,字符变量temp存放弹出的栈顶元素
        scanf("%s",&a); //需要您输入中缀表达式
        LiStack S;//初始化一个栈,用于保存括号和暂时还不能确定运算顺序的运算符
        InitStack(S); //初始化链栈
        int i,j,length=strlen(a); //length为输入的中缀表达式的总长度,i、j分别为静态数组a、b的索引下标
        for(i=j=0;i<length;i++){
            if(a[i]>=48 && a[i]<=57){ //若当前字符是数字,字符0-9的ACSII码范围是[48,57]
                b[j++]=a[i];
                if(a[i+1]=='+'||a[i+1]=='-'||a[i+1]=='*'||a[i+1]=='/') //若下一个字符是运算符,即+、-、*、/,则b加一个空格,以免不同的操作数混在一起
                    b[j++]=' ';
            }
            else if(a[i]=='(')
                Push(S,a[i]); //若当前字符是左括号则直接入栈
            else if(a[i]==')'){ //若当前字符是右括号
                while(StackEmpty(S)==0){ //栈非空则不断弹出栈内字符并加入后缀表达式
                    Pop(S,temp);
                    if(temp=='(') //直到弹出左括号停止,注意这个(不加入后缀表达式
                        break;
                    b[j++]=temp;
                    b[j++]=' '; //加一个空格,从而将字符隔开
                }
            }
            else switch(a[i]){ //若当前字符是运算符
                case '*': case '/':{
                    while(StackEmpty(S)==0){ //若栈非空,则弹出栈中优先级高于或等于当前运算符的所有运算符,并将这些运算符加入后缀表达式
                        Pop(S,temp);
                        if(temp=='/'||temp=='*'){
                            b[j++]=temp;
                            b[j++]=' '; //加一个空格,从而将字符隔开
                        }
                        else if(temp=='('||temp=='-'||temp=='+'){//若栈顶元素是左括号或者是优先级低于当前字符的运算符,则将栈顶元素入栈
                            Push(S,temp);
                            break;
                        }
                    }
                    Push(S,a[i]); //把当前字符入栈
                    break;
                }
                case '-': case '+':{
                    while(StackEmpty(S)==0){ //若栈非空,则弹出栈中优先级高于或等于当前运算符的所有运算符,并将这些运算符加入后缀表达式
                        Pop(S,temp);
                        if(temp=='('){//若栈顶元素是左括号,则将栈顶元素入栈
                            Push(S,temp);
                            break;
                        }
                        else if(temp=='/'||temp=='*'||temp=='-'||temp=='+'){
                            b[j++]=temp;
                            b[j++]=' '; //加一个空格,从而将字符隔开
                        }
                    }
                    Push(S,a[i]); //把当前字符入栈
                    break;
                }
            }
        }
        while(StackEmpty(S)==0){ //栈非空时依次弹出栈顶元素并加入后缀表达式
            Pop(S,temp);
            b[j++]=temp;
            b[j++]=' '; //加一个空格,从而将字符隔开
        }
        printf("结果是:\n");
        for(i=0;i<j;i++) //j是数组中下一个可以插入元素的位置下标,因此b中存放字符的索引区间为[0,j-1]
            printf("%c",b[i]); //输出b中的元素
        printf("\n");
        return 0;
    }
    

    运行程序后需要输入待转换的中缀表达式,下面是三个输入输出示例:

    输入输出
    ((15/(7-(1+1)))*3)-(2+(1+1))15 7 1 1 + - / 3 * 2 1 1 + + -
    2+(3+4)*52 3 4 + 5 * +
    16+2*30/416 2 30 * 4 / +

    2.2 后缀表达式求值

    2.2.1 手算

    后缀表达式求值的手算步骤:从左往右扫描后缀表达式的每一个字符,每遇到一个运算符,就选择运算符左面距离最近的两个操作数执行对应运算,执行运算时注意两个操作数的左右顺序,得到计算结果后去掉刚刚的两个操作数,将新得到的计算结果放在刚刚的这个运算符的位置并代替之,继续从左到右扫描字符直到扫描完全部字符。扫描结束最后得到的就是最终结果。下面是一个示例:

    求值前求值后
    15 7 1 1 + - / 3 * 2 1 1 + + -5
    2 3 4 + 5 * +37
    16 2 30 * 4 / +31

    2.2.2 机算

    需要初始化一个栈,用于存放当前暂时还不能确定运算次序的操作数。用栈实现后缀表达式求值的逻辑过程:

    ① 从左往右扫描后缀表达式的每一个字符,直到扫描完所有字符;

    ② 若扫描到的字符是操作数则压入栈,并回到①,否则执行③;

    ③ 若扫描到的字符是运算符,则连续弹出两个栈顶元素(注意:先出栈的是“右操作数”),然后对这两个操作数执行相应运算,然后再将运算结果入栈,回到①。

    若被扫描的后缀表达式是合法的,则最后栈中只会留下一个元素,就是最终结果。示例代码如下:

    //本程序只能处理有关运算符+、-、*、/的后缀表达式,不能是÷或者×及其他运算
    //本程序不会检查输入的后缀表达式是否正确,因此请您核验好自己的式子是否正确
    //操作数长度在10位以内且必须是整数
    //请将不同的操作数之间、运算符之间、运算符与操作数之间用英文状态的逗号即","隔开
    #include<stdio.h>
    #include<math.h> //pow的头文件,用于求乘方数
    #include<string.h> //strlen的头文件,用于判断字符串长度
    #include<stdlib.h> //malloc、free的头文件
    #define size 50//假定要求值的后缀表达式的字符数在50个以内
    #define num_length 10 //假定后缀表达式中的每一个操作数最长为10位数
    typedef struct Linknode{ //定义链栈及结点
        float data; //数据域
        struct Linknode *next; //指针域
    }*LiStack;
    bool InitStack(LiStack &S){ //链栈的初始化,不带头结点
        S=NULL; //刚开始没有结点
        return true;
    }
    bool Push(LiStack &S,float x){ //将元素x入栈
        Linknode *s=(Linknode *)malloc(sizeof(Linknode)); //创建新结点
        if(s==NULL) //内存不足,创建失败
            return false;
        s->data=x;
        s->next=S; //将结点s作为链栈的栈顶结点
        S=s; //栈顶指针S指向结点s
        return true;
    }
    bool Pop(LiStack &S,float &x){ //栈顶元素出栈,将值赋给x
        if(S==NULL)
            return false; //栈空则返回NULL
        x=S->data;
        Linknode *p=S;
        S=S->next;
        free(p);
        return true;
    }
    int main(){
        char a[size]; //静态数组a存放要处理的后缀表达式
        float right,left,tmp=0; //right,left为弹出栈的元素,依次为右操作数和左操作数
        int b[num_length];//静态数组b存放操作数的各位数字如231的2、3、1
        scanf("%s",&a); //需要您输入后缀表达式
        LiStack S;//初始化一个栈,用于存放当前暂时还不能确定运算次序的操作数
        InitStack(S); //初始化链栈
        int i,j=0,length=strlen(a); //length为输入的后缀表达式的总长度,i、j分别为静态数组a、b的索引下标
        for(i=0;i<length;i++){
            if(a[i]>=48 && a[i]<=57){ //若当前字符是数字,字符0-9的ACSII码范围是[48,57]
                b[j++]=a[i]-48; //字符型的数字减去48就是数字本身,如ASCII码为51的字符为"3",而"3"-48=51-48=3就是数字3本身
                if(a[i+1]==','||a[i+1]=='+'||a[i+1]=='-'||a[i+1]=='*'||a[i+1]=='/'){ //若下一个字符是逗号或者运算符,则代表凑够一个操作数了
                    int m=j;
                    for(int k=0;k<m;k++) // 将分散的各位数字组成一个操作数
                        tmp+=b[k]*int(pow(10,--j));
                    Push(S,tmp); //将当前操作数入栈
                    tmp=0; //在遇到下一个操作数之前将tmp值归零
                }
            }
            else switch(a[i]){ //若当前字符是运算符
                case '*': case '/': case '-': case '+':{
                    Pop(S,right); //先出栈的是“右操作数”
                    Pop(S,left);  //后出栈的是“左操作数”
                    if(a[i]=='+')
                        Push(S,left+right); //执行运算之后将结果入栈,下面三个也是这样
                    else if(a[i]=='-')
                        Push(S,left-right);
                    else if(a[i]=='*')
                        Push(S,left*right);
                    else if(a[i]=='/')
                        Push(S,left/right);
                }
            }
        }
        Pop(S,tmp); //若被扫描的后缀表达式是合法的,则最后栈中只会留下一个元素,就是最终结果
        printf("结果是:%.2f\n",tmp); //输出结果
        return 0;
    }
    

    运行程序后需要输入待求值的后缀表达式,注意本程序只能处理有关运算符+、-、*、/的后缀表达式,不能是÷或者×及其他运算,本程序不会检查输入的后缀表达式是否正确,因此请您核验好自己的式子是否正确,操作数长度在10位以内且必须是整数,请将不同的操作数之间、运算符之间、运算符与操作数之间用英文状态的逗号即","隔开。下面是三个输入输出示例:

    输入输出
    15,7,1,1,+,-,/,3,*,2,1,1,+,+,-5.00
    2,3,4,+,5,*,+37.00
    16,2,30,*,4,/,+31.00

    2.3 后缀表达式转中缀表达式

    2.3.1 手算

    后缀表达式转换成中缀表达式的手算步骤:从左往右扫描后缀表达式的每一个字符,每遇到一个运算符,就选择运算符左面距离最近的两个操作数,将【左操作数 右操作数 运算符】变为(左操作数 运算符 右操作数)的形式。注意两个操作数的左右顺序,得到一个式子后去掉刚刚的两个操作数,将得到的式子放在刚刚的这个运算符的位置并代替之,继续从左到右扫描字符直到扫描完全部字符。扫描结束最后得到的式子就是最终结果。下面是一个示例:

    转换前的后缀表达式转换后的中缀表达式
    15 7 1 1 + - / 3 * 2 1 1 + + -(((15/(7-(1+1)))*3)-(2+(1+1)))
    2 3 4 + 5 * +(2+((3+4)*5))
    16 2 30 * 4 / +(16+((2*30)/4))

    2.3.2 机算

    需要初始化一个栈,用于存放当前暂时还不能确定运算次序的操作数。用栈实现后缀表达式转中缀表达式的逻辑过程:

    ① 从左往右扫描下一个元素,直到处理完所有元素;

    ② 若扫描到操作数则压入栈,并回到①,否则执行③;

    ③ 若扫描到运算符,则弹出两个栈顶元素(注意:先出栈的是“右操作数”),构成(左操作数 运算符 右操作数),然后将其压回栈顶,回到①。

    若被扫描的后缀表达式是合法的,则最后栈中只会留下一个元素,就是最终结果。示例代码如下:

    //本程序只能处理有关运算符+、-、*、/的后缀表达式,不能是÷或者×及其他运算
    //本程序不会检查输入的后缀表达式是否正确,因此请您核验好自己的式子是否正确
    //操作数长度在10位以内且必须是整数
    //请将不同的操作数之间、运算符之间、运算符与操作数之间用英文状态的逗号即","隔开
    #include<stdio.h>
    #include<string.h> //strlen的头文件,用于判断字符串长度
    #include<stdlib.h> //malloc、free的头文件
    #define size 50//假定输入的后缀表达式的字符数在50以内
    #define num_length 10 //假定每一个操作数最长为10位数
    typedef struct Linknode{ //定义链栈及结点
        char data[size]; //数据域
        struct Linknode *next; //指针域
    }*LiStack;
    bool InitStack(LiStack &S){ //链栈的初始化,不带头结点
        S=NULL; //刚开始没有结点
        return true;
    }
    bool Push(LiStack &S,char *x){ //将元素x入栈
        Linknode *s=(Linknode *)malloc(sizeof(Linknode)); //创建新结点
        if(s==NULL||strlen(x)>size) //内存不足或者长度超过size,则失败
            return false;
        int i;
        for(i=0;i<strlen(x);i++)
            s->data[i]=x[i];
        s->data[i]='\0';
        s->next=S; //将结点s作为栈顶结点
        S=s; //栈顶指针S指向结点s
        return true;
    }
    bool Pop(LiStack &S,char *x){ //栈顶元素出栈,将值赋给x
        if(S==NULL)
            return false; //栈空则返回NULL
        Linknode *p=S; //p指向栈顶结点
        int i;
        for(i=0;p->data[i]!='\0';i++)
            x[i]=p->data[i];
        x[i]='\0';
        S=p->next;
        free(p);
        return true;
    }
    int main(){
        char a[size]; //静态数组a存放要处理的后缀表达式
        char right[size],left[size]; //right,left为弹出栈的元素,依次为右操作数和左操作数
        char b[num_length];//静态数组b存放操作数的各位数字如231的'2'、'3'、'1'
        scanf("%s",&a); //需要您输入后缀表达式
        LiStack S;//初始化一个栈,用于存放当前暂时还不能确定运算次序的字符串形式的操作数
        InitStack(S); //初始化链栈
        int i,j=0,length=strlen(a); //length为输入的后缀表达式的总长度,i、j分别为静态数组a、b的索引下标
        for(i=0;i<length;i++){
            if(a[i]>=48&&a[i]<=57){ //若当前字符是数字,字符0-9的ACSII码范围是[48,57]
                b[j++]=a[i];
                if(a[i+1]==','||a[i+1]=='+'||a[i+1]=='-'||a[i+1]=='*'||a[i+1]=='/'){ //若下一个字符是逗号或者运算符,则代表凑够一个操作数了
                    b[j]='\0';
                    Push(S,b); //将当前操作数入栈
                    j=0; //将j归零
                }
            }
            else switch(a[i]){
                case '*': case '/': case '-': case '+':{ //若当前字符是运算符
                    Pop(S,right); //先出栈的是“右操作数”
                    Pop(S,left);  //后出栈的是“左操作数”
                    if(strlen(left)+strlen(right)+1+2>size) // 左右操作数长度之和再加上操作符、左右括号的长度过长,容不下
                        return false;
                    char tmp[size]; //临时变量
                    tmp[0]='('; //先存左括号
                    int k;
                    for(k=0;k<strlen(left);k++)
                        tmp[k+1]=left[k]; //存左操作数
                    tmp[strlen(left)+1]=a[i]; //存运算符
                    for(k=0;k<strlen(right);k++)
                        tmp[k+strlen(left)+2]=right[k]; //存右操作数
                    tmp[strlen(left)+strlen(right)+2]=')'; //最后存右括号
                    tmp[strlen(left)+strlen(right)+3]='\0';
                    Push(S,tmp); //将结果入栈
                }
            }
        }
        char c[size];
        Pop(S,c); //若被扫描的后缀表达式是合法的,则最后栈中只会留下一个元素,就是最终结果
        printf("结果是:%s\n",c); //输出结果
        return 0;
    }
    

    运行程序后需要输入待转换的后缀表达式,注意本程序只能处理有关运算符+、-、*、/的后缀表达式,不能是÷或者×及其他运算,本程序不会检查输入的后缀表达式是否正确,因此请您核验好自己的式子是否正确,操作数长度在10位以内且必须是整数,请将不同的操作数之间、运算符之间、运算符与操作数之间用英文状态的逗号即","隔开。下面是三个输入输出示例:

    输入输出
    15,7,1,1,+,-,/,3,*,2,1,1,+,+,-(((15/(7-(1+1)))*3)-(2+(1+1)))
    2,3,4,+,5,*,+(2+((3+4)*5))
    16,2,30,*,4,/,+(16+((2*30)/4))

    3 前缀表达式相关考点

    3.1 中缀表达式转前缀表达式

    3.1.1 手算

    中缀转前缀的手算步骤:

    ① 确定中缀表达式中各个运算符的运算顺序,但是有时候运算顺序不唯一,因此对应的前缀表达式也不唯一。为了保证手算和机算结果相同,且保证运算顺序唯一,请遵从“右优先”原则:只要右边的运算符能先计算,就优先算右边的。确定完运算符的运算顺序后,如果有界限符即括号,就可以去掉全部的括号了,或者说可以忽略括号的存在继续下面步骤;

    ② 选择下一个运算符,按照【运算符 左操作数 右操作数】的方式组合成一个新的式子,然后放在原来操作符的位置。如果还有运算符没被处理,就继续②,否则最后得到的式子就是最终结果。下面是一个示例:

    转换前的中缀表达式转换后的前缀表达式
    ((15/(7-(1+1)))*3)-(2+(1+1))- * / 15 - 7 + 1 1 3 + 2 + 1 1
    2+(3+4)*5+ 2 * + 3 4 5
    16+2*30/4+ 16 * 2 / 30 4

    3.1.2 机算

    实现中缀表达式转前缀表达式的逻辑过程:初始化一个栈,用于保存暂时还不能确定运算顺序的运算符。从右到左扫描中缀表达式的各个字符,直到末尾。在扫描时可能遇到三种情况:

    ① 当前字符是数字:直接加入前缀表达式,然后处理下一个字符;

    ② 当前字符是括号,又分为两种情况:

    • 1)当前字符是右括号即)则直接将当前字符入栈,然后处理下一个字符;
    • 2)当前字符是左括号即(:若栈空则直接处理下一个字符。若栈非空则不断弹出栈顶元素——若弹出右括号)后则停止继续弹出(注意这个右括号)不加入前缀表达式)并直接处理下一个字符,否则将栈顶元素加入前缀表达式,然后继续弹出栈顶元素;

    ③ 当前字符是运算符,又分为两种情况:

    • 1)栈空则直接把当前字符入栈,然后处理下一个字符;
    • 2)栈非空则不断弹出栈顶元素:若栈顶元素是右括号)或优先级高于当前字符的运算符则停止栈顶元素的弹出,再将栈顶元素再次入栈,之后再把当前字符入栈,然后处理下一个字符。若栈顶元素是运算符且优先级低于或等于当前字符,则将栈顶元素加入前缀表达式,然后继续弹出栈顶元素;

    按上述方法处理完所有字符后,若栈非空则将栈中剩余字符依次弹出并依次加入前缀表达式。将最后得到的前缀表达式倒置就是最终结果。示例代码如下:

    //本程序只能处理有关运算符+、-、*、/的中缀表达式,不能是÷或者×及其他运算
    //界限符只能是英文状态的左右括号即'('、')',操作数只能是整数
    //本程序不会检查输入的中缀表达式是否正确,因此请您核验好自己的式子是否正确
    #include<stdio.h>
    #include<string.h> //strlen的头文件,用于判断字符串长度
    #include<stdlib.h> //malloc、free的头文件
    #define size 50//假定要转换的中缀表达式的字符数在50个以内
    typedef struct Linknode{ //定义链栈及结点
        char data; //数据域
        struct Linknode *next; //指针域
    }*LiStack;
    bool InitStack(LiStack &S){ //链栈的初始化,不带头结点
        S=NULL; //刚开始没有结点
        return true;
    }
    bool StackEmpty(LiStack S){ //判断栈空
        return S==NULL;
    }
    bool Push(LiStack &S,char x){ //将元素x入栈
        Linknode *s=(Linknode *)malloc(sizeof(Linknode)); //创建新结点
        if(s==NULL) //内存不足,创建失败
            return false;
        s->data=x;
        s->next=S; //将结点s作为链栈的栈顶结点
        S=s; //栈顶指针S指向结点s
        return true;
    }
    bool Pop(LiStack &S,char &x){ //栈顶元素出栈,将值赋给x
        if(S==NULL)
            return false; //栈空则返回NULL
        x=S->data;
        Linknode *p=S;
        S=S->next;
        free(p);
        return true;
    }
    int main(){
        char temp,a[size],b[size]; //静态数组a、b分别存放要转换的中缀表达式和转换后的前缀表达式,字符变量temp存放弹出的栈顶元素
        scanf("%s",&a); //需要您输入中缀表达式
        LiStack S;//初始化一个栈,用于保存括号和暂时还不能确定运算顺序的运算符
        InitStack(S); //初始化链栈
        int i,j,length=strlen(a); //length为输入的中缀表达式的总长度,i、j分别为静态数组a、b的索引下标
        for(i=length-1,j=0;i>=0;i--){ //从右到左扫描中缀表达式的各个字符,直到末尾
            if(a[i]>=48 && a[i]<=57){ //若当前字符是数字,字符0-9的ACSII码范围是[48,57]
                b[j++]=a[i];
                if(a[i-1]=='+'||a[i-1]=='-'||a[i-1]=='*'||a[i-1]=='/') //若上一个字符是运算符,即+、-、*、/,则b加一个空格,以免不同的操作数混在一起
                    b[j++]=' ';
            }
            else if(a[i]==')')
                Push(S,a[i]); //若当前字符是右括号则直接入栈
            else if(a[i]=='('){ //若当前字符是左括号
                while(StackEmpty(S)==0){ //栈非空则不断弹出栈内字符并加入前缀表达式
                    Pop(S,temp);
                    if(temp==')') //直到弹出右括号停止,注意这个)不加入前缀表达式
                        break;
                    b[j++]=temp;
                    b[j++]=' '; //加一个空格,从而将字符隔开
                }
            }
            else switch(a[i]){ //若当前字符是运算符
                case '*': case '/':{
                    while(StackEmpty(S)==0){ //若栈非空,则弹出栈中优先级低于或等于当前运算符的所有运算符,并将这些运算符加入前缀表达式
                        Pop(S,temp);
                        if(temp=='+'||temp=='-'||temp=='/'||temp=='*'){
                            b[j++]=temp;
                            b[j++]=' '; //加一个空格,从而将字符隔开
                        }
                        else if(temp==')'){ //若栈顶元素是右括号或者是优先级高于当前字符的运算符,则将栈顶元素入栈
                            Push(S,temp);
                            break;
                        }
                    }
                    Push(S,a[i]); //把当前字符入栈
                    break;
                }
                case '-': case '+':{
                    while(StackEmpty(S)==0){ //若栈非空,则弹出栈中优先级低于或等于当前运算符的所有运算符,并将这些运算符加入前缀表达式
                        Pop(S,temp);
                        if(temp==')'||temp=='*'||temp=='/'){ //若栈顶元素是右括号或者是优先级高于当前字符的运算符,则将栈顶元素入栈
                            Push(S,temp);
                            break;
                        }
                        else if(temp=='+'||temp=='-'){
                            b[j++]=temp;
                            b[j++]=' '; //加一个空格,从而将字符隔开
                        }
                    }
                    Push(S,a[i]); //把当前字符入栈
                    break;
                }
            }
        }
        while(StackEmpty(S)==0){ //栈非空时依次弹出栈顶元素并加入前缀表达式
            Pop(S,temp);
            b[j++]=temp;
            b[j++]=' '; //加一个空格,从而将字符隔开
        }
        printf("结果是:\n");
        for(i=j-1;i>=0;i--) //b中存放字符的索引区间为[0,j-1]
            printf("%c",b[i]); //倒序输出b中的元素
        printf("\n");
        return 0;
    }
    

    运行程序后需要输入待转换的中缀表达式,下面是三个输入输出示例:

    输入输出
    (((15/(7-(1+1)))*3)-(2+(1+1)))- * /15 -7 +1 1 3 +2 +1 1
    (2+((3+4)*5))+2 * +3 4 5
    (16+(2*(30/4)))+16 *2 /30 4

    3.2 前缀表达式求值

    3.2.1 手算

    前缀表达式求值的手算步骤:从右往左扫描前缀表达式的每一个字符,每遇到一个运算符,就选择运算符右面距离最近的两个操作数执行对应运算,执行运算时注意两个操作数的左右顺序,得到计算结果后去掉刚刚的两个操作数,将新得到的计算结果放在刚刚的这个运算符的位置并代替之,继续从右到左扫描字符直到扫描完全部字符。扫描结束最后得到的就是最终结果。下面是一个示例:

    求值前求值后
    - * / 15 - 7 + 1 1 3 + 2 + 1 15
    + 2 * + 3 4 537
    + 16 * 2 / 30 431

    3.2.2 机算

    需要初始化一个栈,用于存放当前暂时还不能确定运算次序的操作数。用栈实现前缀表达式求值的逻辑过程:

    ① 从右往左扫描前缀表达式的每一个字符,直到扫描完所有字符;

    ② 若扫描到的字符是操作数则压入栈,并回到①,否则执行③;

    ③ 若扫描到的字符是运算符,则连续弹出两个栈顶元素(注意:先出栈的是“左操作数”),然后对这两个操作数执行相应运算,然后再将运算结果入栈,回到①。

    若被扫描的前缀表达式是合法的,则最后栈中只会留下一个元素,就是最终结果。示例代码如下:

    //本程序只能处理有关运算符+、-、*、/的前缀表达式,不能是÷或者×及其他运算
    //本程序不会检查输入的前缀表达式是否正确,因此请您核验好自己的式子是否正确
    //操作数长度在10位以内且必须是整数
    //请将不同的操作数之间、运算符之间、运算符与操作数之间用英文状态的逗号即","隔开
    #include<stdio.h>
    #include<math.h> //pow的头文件,用于求乘方数
    #include<string.h> //strlen的头文件,用于判断字符串长度
    #include<stdlib.h> //malloc、free的头文件
    #define size 50//假定要求值的前缀表达式的字符数在50个以内
    #define num_length 10 //假定前缀表达式中的每一个操作数最长为10位数
    typedef struct Linknode{ //定义链栈及结点
        float data; //数据域
        struct Linknode *next; //指针域
    }*LiStack;
    bool InitStack(LiStack &S){ //链栈的初始化,不带头结点
        S=NULL; //刚开始没有结点
        return true;
    }
    bool Push(LiStack &S,float x){ //将元素x入栈
        Linknode *s=(Linknode *)malloc(sizeof(Linknode)); //创建新结点
        if(s==NULL) //内存不足,创建失败
            return false;
        s->data=x;
        s->next=S; //将结点s作为链栈的栈顶结点
        S=s; //栈顶指针S指向结点s
        return true;
    }
    bool Pop(LiStack &S,float &x){ //栈顶元素出栈,将值赋给x
        if(S==NULL)
            return false; //栈空则返回NULL
        x=S->data;
        Linknode *p=S;
        S=S->next;
        free(p);
        return true;
    }
    int main(){
        char a[size]; //静态数组a存放要处理的前缀表达式
        float right,left,tmp=0; //right,left为弹出栈的元素,依次为右操作数和左操作数
        int b[num_length];//静态数组b存放操作数的各位数字如231的2、3、1
        scanf("%s",&a); //需要您输入前缀表达式
        LiStack S;//初始化一个栈,用于存放当前暂时还不能确定运算次序的操作数
        InitStack(S); //初始化链栈
        int i,j=0,length=strlen(a); //length为输入的前缀表达式的总长度,i、j分别为静态数组a、b的索引下标
        for(i=length-1;i>=0;i--){ //从右到左扫描
            if(a[i]>=48 && a[i]<=57){ //若当前字符是数字,字符0-9的ACSII码范围是[48,57]
                b[j++]=a[i]-48; //字符型的数字减去48就是数字本身,如ASCII码为51的字符为"3",而"3"-48=51-48=3就是数字3本身
                if(a[i-1]==','||a[i-1]=='+'||a[i-1]=='-'||a[i-1]=='*'||a[i-1]=='/'){ //若上一个字符是逗号或者运算符,则代表凑够一个操作数了
                    int m=j;
                    for(int k=0;k<m;k++) // 将分散的各位数字组成一个操作数
                        tmp+=b[k]*int(pow(10,k));
                    Push(S,tmp); //将当前操作数入栈
                    tmp=0; //在遇到下一个操作数之前将tmp值归零
                    j=0;
                }
            }
            else switch(a[i]){ //若当前字符是运算符
                case '*': case '/': case '-': case '+':{
                    Pop(S,left);  //先出栈的是“左操作数”
                    Pop(S,right); //后出栈的是“右操作数”
                    if(a[i]=='+')
                        Push(S,left+right); //执行运算之后将结果入栈,下面三个也是这样
                    else if(a[i]=='-')
                        Push(S,left-right);
                    else if(a[i]=='*')
                        Push(S,left*right);
                    else if(a[i]=='/')
                        Push(S,left/right);
                }
            }
        }
        Pop(S,tmp); //若被扫描的前缀表达式是合法的,则最后栈中只会留下一个元素,就是最终结果
        printf("结果是:%.2f\n",tmp); //输出结果
        return 0;
    }
    

    运行程序后需要输入待求值的前缀表达式,注意本程序只能处理有关运算符+、-、*、/的前缀表达式,不能是÷或者×及其他运算,本程序不会检查输入的前缀表达式是否正确,因此请您核验好自己的式子是否正确,操作数长度在10位以内且必须是整数,请将不同的操作数之间、运算符之间、运算符与操作数之间用英文状态的逗号即","隔开。下面是三个输入输出示例:

    输入输出
    +,16,*,2,/,30,431.00
    +,2,*,+,3,4,537.00
    -,*,/,15,-,7,+,1,1,3,+,2,+,1,15.00

    3.3 前缀表达式转中缀表达式

    3.3.1 手算

    前缀表达式转换成中缀表达式的手算步骤:从右往左扫描前缀表达式的每一个字符,每遇到一个运算符,就选择运算符右面距离最近的两个操作数,将【运算符 左操作数 右操作数】变为(左操作数 运算符 右操作数)的形式。注意两个操作数的左右顺序,得到一个式子后去掉刚刚的两个操作数,将得到的式子放在刚刚的这个运算符的位置并代替之,继续从右到左扫描字符直到扫描完全部字符。扫描结束最后得到的式子就是最终结果。下面是一个示例:

    转换前的前缀表达式转换后的中缀表达式
    - * / 15 - 7 + 1 1 3 + 2 + 1 1(((15/(7-(1+1)))*3)-(2+(1+1)))
    + 16 * 2 / 30 4(16+(2*(30/4)))
    + 2 * + 3 4 5(2+((3+4)*5))

    3.3.2 机算

    需要初始化一个栈,用于存放当前暂时还不能确定运算次序的操作数。用栈实现前缀表达式转中缀表达式的逻辑过程:

    ① 从右往左扫描下一个元素,直到处理完所有元素;

    ② 若扫描到操作数则压入栈,并回到①,否则执行③;

    ③ 若扫描到运算符,则弹出两个栈顶元素(注意:先出栈的是“左操作数”),构成(左操作数 运算符 右操作数),然后将其压回栈顶,回到①。

    若被扫描的前缀表达式是合法的,则最后栈中只会留下一个元素,就是最终结果。示例代码如下:

    //本程序只能处理有关运算符+、-、*、/的前缀表达式,不能是÷或者×及其他运算
    //本程序不会检查输入的前缀表达式是否正确,因此请您核验好自己的式子是否正确
    //操作数长度在10位以内且必须是整数
    //请将不同的操作数之间、运算符之间、运算符与操作数之间用英文状态的逗号即","隔开
    #include<stdio.h>
    #include<string.h> //strlen的头文件,用于判断字符串长度
    #include<stdlib.h> //malloc、free的头文件
    #define size 50//假定输入的前缀表达式的字符数在50以内
    #define num_length 10 //假定每一个操作数最长为10位数
    typedef struct Linknode{ //定义链栈及结点
        char data[size]; //数据域
        struct Linknode *next; //指针域
    }*LiStack;
    bool InitStack(LiStack &S){ //链栈的初始化,不带头结点
        S=NULL; //刚开始没有结点
        return true;
    }
    bool Push(LiStack &S,char *x){ //将元素x入栈
        Linknode *s=(Linknode *)malloc(sizeof(Linknode)); //创建新结点
        if(s==NULL||strlen(x)>size) //内存不足或者长度超过size,则失败
            return false;
        int i;
        for(i=0;i<strlen(x);i++)
            s->data[i]=x[i];
        s->data[i]='\0';
        s->next=S; //将结点s作为栈顶结点
        S=s; //栈顶指针S指向结点s
        return true;
    }
    bool Pop(LiStack &S,char *x){ //栈顶元素出栈,将值赋给x
        if(S==NULL)
            return false; //栈空则返回NULL
        Linknode *p=S; //p指向栈顶结点
        int i;
        for(i=0;p->data[i]!='\0';i++)
            x[i]=p->data[i];
        x[i]='\0';
        S=p->next;
        free(p);
        return true;
    }
    int main(){
        char a[size]; //静态数组a存放要处理的前缀表达式
        char right[size],left[size],tmp[size]; //right,left为弹出栈的元素,依次为右操作数和左操作数;tmp是临时变量,用于存储某些字符串
        char b[num_length];//静态数组b存放操作数的各位数字如231的'2'、'3'、'1'
        scanf("%s",&a); //需要您输入前缀表达式
        LiStack S;//初始化一个栈,用于存放当前暂时还不能确定运算次序的字符串形式的操作数
        InitStack(S); //初始化链栈
        int i,j=0,length=strlen(a); //length为输入的前缀表达式的总长度,i、j分别为静态数组a、b的索引下标
        for(i=length-1;i>=0;i--){ //从右到左扫描
            if(a[i]>=48&&a[i]<=57){ //若当前字符是数字,字符0-9的ACSII码范围是[48,57]
                b[j++]=a[i];
                if(a[i-1]==','||a[i-1]=='+'||a[i-1]=='-'||a[i-1]=='*'||a[i-1]=='/'){ //若下一个字符是逗号或者运算符,则代表凑够一个操作数了
                    int m;
                    for(m=0;m<j;m++)
                        tmp[m]=b[j-1-m]; //因为是从右到左扫描的,因此需要将数字颠倒一下
                    tmp[m]='\0';
                    Push(S,tmp); //将当前操作数入栈
                    j=0; //将j归零
                }
            }
            else switch(a[i]){
                case '*': case '/': case '-': case '+':{ //若当前字符是运算符
                    Pop(S,left);  //先出栈的是“左操作数”
                    Pop(S,right); //后出栈的是“右操作数”
                    if(strlen(left)+strlen(right)+1+2>size) // 左右操作数长度之和再加上操作符、左右括号的长度过长,容不下
                        return false;
                    tmp[0]='('; //先存左括号
                    int k;
                    for(k=0;k<strlen(left);k++)
                        tmp[k+1]=left[k]; //存左操作数
                    tmp[strlen(left)+1]=a[i]; //存运算符
                    for(k=0;k<strlen(right);k++)
                        tmp[k+strlen(left)+2]=right[k]; //存右操作数
                    tmp[strlen(left)+strlen(right)+2]=')'; //最后存右括号
                    tmp[strlen(left)+strlen(right)+3]='\0';
                    Push(S,tmp); //将结果入栈
                }
            }
        }
        Pop(S,tmp); //若被扫描的前缀表达式是合法的,则最后栈中只会留下一个元素,就是最终结果
        printf("结果是:%s\n",tmp); //输出结果
        return 0;
    }
    

    运行程序后需要输入待转换的前缀表达式,注意本程序只能处理有关运算符+、-、*、/的前缀表达式,不能是÷或者×及其他运算,本程序不会检查输入的前缀表达式是否正确,因此请您核验好自己的式子是否正确,操作数长度在10位以内且必须是整数,请将不同的操作数之间、运算符之间、运算符与操作数之间用英文状态的逗号即","隔开。下面是三个输入输出示例:

    输入输出
    +,16,*,2,/,30,4(16+(2*(30/4)))
    +,2,*,+,3,4,5(2+((3+4)*5))
    -,*,/,15,-,7,+,1,1,3,+,2,+,1,1(((15/(7-(1+1)))*3)-(2+(1+1)))

    END

    展开全文
  • 前缀表达式的计算机求值

    千次阅读 2019-04-24 15:11:57
    前缀表达式的计算机求值特点 引例:某表达式的前缀形式为"±*^ABCD/E/F+GH",那么它的中缀形式为? 前缀表达式的操作 前缀表达式是一种没有括号的算术表达式,就是前序表达式,不同于中缀表达式,它把运算符写在...

    前缀表达式的计算机求值特点

    引例:某表达式的前缀形式为"+ -*^ABCD/E/F+GH",那么它的中缀形式为?

    前缀表达式的操作

    前缀表达式是一种没有括号的算术表达式,就是前序表达式,不同于中缀表达式,它把运算符写在前面,操作数写在后面,前缀表达式也称为“波兰式”。例如,- 1 + 2 3,它等价于1-(2+3)。后缀表达式和前缀表达式十分相似,只是后缀表达式从左往右读入计算机。
    前缀表达式:从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。

    计算过程:题目中前缀形式为:±*^ABCD/E/F+GH

    1. 首先扫描 H,是数字 入栈 ,栈中为: H
      2)扫描 G 为数字 入栈 ,栈中为:G,H
      3)扫描+ 为运算符 ,依次弹出G ,H ,得到 G+H 的结果 入栈,栈中为: G+H(在这里方便讲解 标记为 G+H)
      4)扫描 F 为数字 ,入栈 ,栈中为 F, G+H
      5)扫描 / 为运算符, 依次弹出 F,G+H ,计算F/(G+H) 的结果入栈 ,栈中为 F/(G+H)
      6)扫描 E 为数字,入栈,栈中为 E, F/(G+H)
      7)扫描 / 为运算符, 依次弹出E, F/(G+H) ,计算 E/(F/(G+H))
      8)扫描 D 为数字,入栈 栈中为:D, E/(F/(G+H))
      9)扫描 C 为数字,入栈 栈中为:C,D, E/(F/(G+H))
      10)扫描 B 为数字,入栈 栈中为:B,C,D, E/(F/(G+H))
      11)扫描 A 为数字,入栈 栈中为:A,B,C,D, E/(F/(G+H))
      12)扫描^ 为运算符,依次弹出 A,B 计算 A^B的结果入栈, 栈中为:A^B ,C,D, E/(F/(G+H))
      13)扫描为运算符,依次弹出 A^B,C 计算 A^BC的结果入栈, 栈中为:A^B* C,D, E/(F/(G+H))
      14)扫描-为运算符,依次弹出 A^BC,D 计算 A^BC-D的结果入栈, 栈中为:A^B* C-D, E/(F/(G+H))
      15)扫描+为运算符,依次弹出 A^BC-D, E/(F/(G+H)) 计算 A^BC-D+ E/(F/(G+H)) 的到结果
      最后得到的表达式为: A^B* C-D+ E/(F/(G+H))

    代码实现中缀2前缀

    中缀表达式转前缀表达式,利用前缀表达式求结果。

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    /**
     * @Auther: 我爱双面奶
     * @Date: 2018/7/18 22:53
     * @Description: 中缀(infix)表达式转波兰式(polish notation)(前缀表达式)
     *
     */
    public class InfixToPNCalculate {
    
        public static void main(String[] args) {
            String str = "1+(6/2)-8*2+(20-4)";
            List<String> pnStack = infixToPn(str);
            int result = getResrult(pnStack);
            System.out.println("结果:"+result);
        }
    
        /**
         * 中缀转前缀表达式算法
         *
         * 1、初始化两个栈:运算符栈opStack和存储前缀表达式栈pnStack;
         * 2、【反转】字符串,【从左至右】扫描中缀表达式;
         * 3、遇到操作数时,直接将其压入tempStack中;
         * 4、遇到运算符时,比较其与opStack栈顶运算符的优先级:
         *       4.1、如果opStack为空,或者栈顶运算符为右括号’)’,则直接将此运算符压入opStack中;
         *       4.2、否则,若优先级比栈顶运算符的优先级高或相等,则直接将此运算符压入opStack中;
         *       4.3、否则,将opStack栈顶的运算符弹出并压入到tempStack中,再次转入步骤4,与opStack中新的栈顶运算符相比较;
         * 5、遇到括号时:
         *       5.1、如果是右括号’)’,则直接压入opStack中;
         *       5.2、如果是左括号’(‘,则依次弹出opStack栈顶的运算符并压入tempStack中,知道遇到右括号’)’为止,此时将这一对括号丢弃;
         * 6、重复步骤2~5,直到表达式的最左边;
         * 7、将opStack中剩余的运算符依次弹出并压入tempStack中;
         * 8、依次弹出tempStack中的元素保存到result中,result即为中缀表达式转换所得的前缀表达式。
         * @param strExpression 前缀表达式
         * @return 后缀表达式
         */
        public static List<String> infixToPn(String strExpression){
            StringBuilder stringBuilder = new StringBuilder(strExpression.trim());//将String对象转换为StringBuilder对象,为了转字符串
            System.out.println("中缀表达式:"+stringBuilder);
            stringBuilder = stringBuilder.reverse();//反转字符串
            List<String> pnStack = new ArrayList();//前缀表达式栈
            List<String> opStack = new ArrayList();//运算符栈
    
            String falg = "";
            char[] str = stringBuilder.toString().toCharArray();
            //从左往右扫描
            for(int i=0;i<str.length;i++ ){
                if(isDigit((falg+str[i]).trim())){//判断flag+当前字符是否为数字
                    falg = (falg+str[i]).trim();
                    if(i==str.length-1){//当当前字符是数字,并且是最后一个字符时直接存入前缀表达式栈
                        //由于之前反转了,现在要反转回来,比如45在之前被反转为了54,需要反转回来
                        pnStack.add(new StringBuilder(falg).reverse().toString());
                    }
                }else {//当当前字符不是数字时
                    if(falg.trim()!=""&&isDigit((falg).trim())){//将上一次的flag存入前缀表达式栈
                        pnStack.add(new StringBuilder(falg).reverse().toString());
                        falg="";
                    }
                    if(opStack.size()==0||opStack.get(opStack.size()-1).equals(")")){//对应4.1
                        opStack.add(String.valueOf(str[i]));
                    }else if(str[i]==')'){//对应5.1
                        opStack.add(String.valueOf(str[i]));
                    }else if(str[i]=='('){//对应5.2
                        while (opStack.size()!=0){
                            if(opStack.get(opStack.size()-1).equals(")")){
                                opStack.remove(opStack.size()-1);
                                break;
                            }
                            pnStack.add(opStack.get(opStack.size()-1));
                            opStack.remove(opStack.size()-1);
                        }
                    }else if (str[i]=='*'||str[i]=='/'){//对应4.2
                        opStack.add(String.valueOf(str[i]));
                    }else if(opStack.get(opStack.size()-1).equals("*")||opStack.get(opStack.size()-1).equals("/")){//对应4.3
                        pnStack.add(opStack.get(opStack.size()-1));
                        opStack.remove(opStack.size()-1);
                        i--;
                    }else {//对应4.2
                        opStack.add(String.valueOf(str[i]));
                    }
                }
            }
            //对应7
            while (opStack.size()!=0){
                pnStack.add(opStack.get(opStack.size()-1));
                opStack.remove(opStack.size()-1);
            }
            //反转List对象
            Collections.reverse(pnStack);
            System.out.print("波兰式(前缀表达式):");
            pnStack.stream().forEach(x-> System.out.print(x+" "));//迭代输出
            System.out.println("");
            return pnStack;
        }
    
        /**
         * 通过前缀表达式计算结果
         * 1、借助中间结果栈tempStack,【从右至左】扫描表达式
         * 2、遇到操作数时,将操作数入tempStack栈
         * 3、遇到操作符时,从tempStack栈中弹出两个操作数,进行运行,然后将运算结果压入tempStack栈。
         * 4、重复1~3,直到pnStack为空
         * 5、tempStack栈剩下的最后一个元素即所求结果
         * @param pnStack 中间结果栈
         * @return
         */
        public static int getResrult(List<String> pnStack){
            int result = 0;
            List<String> tempResultStack = new ArrayList<>();
    
            while (pnStack.size()!=0){
                int end = pnStack.size()-1;
                int resultend = tempResultStack.size()-1;
                if(isDigit(pnStack.get(end))){//对应2
                    tempResultStack.add(pnStack.get(end));
                    pnStack.remove(end);
                }else {//对应3
                    if(pnStack.get(end).equals("*")) {
                        result = Integer.parseInt(tempResultStack.get(resultend)) * Integer.parseInt(tempResultStack.get((resultend - 1)));
                    }else if (pnStack.get(end).equals("/")){
                        result = Integer.parseInt(tempResultStack.get(resultend)) / Integer.parseInt(tempResultStack.get((resultend - 1)));
                    }else if (pnStack.get(end).equals("+")){
                        result = Integer.parseInt(tempResultStack.get(resultend)) + Integer.parseInt(tempResultStack.get((resultend - 1)));
                    }else if (pnStack.get(end).equals("-")){
                        result = Integer.parseInt(tempResultStack.get(resultend)) - Integer.parseInt(tempResultStack.get((resultend - 1)));
                    }
                    pnStack.remove(end);
                    tempResultStack.remove(resultend);
                    tempResultStack.remove(resultend-1);
                    tempResultStack.add(String.valueOf(result));
                }
            }
           // System.out.println(tempResultStack.toString());
            return result;
        }
    
        /**
         * 判断一个字符串是否为数值
         * @param str 判断的字符串
         * @return 返回一个boolean值
         */
        public static boolean isDigit(String str){
            return str.matches("[0-9]{1,}");
        }
    
    }
    

    附录

    1.代码参考作者:我爱双面奶
    https://note.youdao.com/ynoteshare1/index.html?id=ffe93536b1140b00bbe205282990e1ff&type=note
    2.题目来自牛客网

    展开全文
  • 表达式 表达式有三种表示方法:运算符所在不同位置命名 Exp = S1 + OP + S2 中缀表达法 Exp = OP + S1 + S2 前缀表达法 Exp = S1 + S2 + OP 后缀表达法 ...前缀表达式 Exp = OP S1 S2 【讨论】 Exp = + ×a...
  • preToIn:一种使用堆栈将前缀表达式转换为后缀表达式的算法
  • 题目:前缀表达式和后缀表达式的文法分别为:前e->*(e.e)|+(e.e)|a后e->(e.e)*|(e.e)+|a编一个程序。输入一个前缀表达式,输出一个与之等价的后缀表达式:假设输入的前缀表达式没有语法错误。例如:输入+(*(a,+...
  • 文章目录中缀表达式前缀表达式前缀求值中缀变前缀前缀变中缀后缀表达式中缀变后缀后缀变中缀后缀求值 中缀表达式     中缀即我们平时用的数学表达式,其递归定义为中缀表达式 运算符 中缀表达式。举例:1+2,(1...
  • 前缀表达式 前缀表达式又称波兰式,前缀表达式的运算符位于操作符之前。 例:(3+4)*5-6对应的前缀表达式就是 - * + 3 4 5 6 如何将中缀表达式(3+4)*5-6转换成前缀表达式 - * + 3 4 5 6。 将中缀表达式转换为前缀...
  • 一、求前缀表达式计算值 (1)从右到左扫描表达式,遇到数字时直接入栈,遇到运算符时弹出栈顶两个数; (2)根据运算符对两个数进行相应计算(栈顶元素 op 次顶元素),并将计算结果入栈; (3)重复上述过程直至...
  • 相对应的还有前缀表达式(Prefix Notation),如:"+ - A * B C D",转换成中缀表达式为:"A - B * C + D";后缀表达式 (Postfix Notation),比如前所述的中缀表达式转换为后缀表达式为:"A B C * - D +"。 四、...
  • 中缀表达式转前缀表达式求值 首先将中缀表达式转换成前缀表达式 前缀表达式中,操作符在前 例如:1+2*(5-3)+4 后缀表达式:++1*2-534 一、转换思路 转换思路为将输入的中缀表达式字符串从右往左扫描(字符前后加#号)...
  • 前缀表达式是一种没有括号的算术表达式,与中缀表达式不同的是,其将运算符写在前面,操作数写在后面。后缀表达式则是将操作数写在前面,运算符写在后面。 前缀表达式又称波兰表达式,后缀表达式又称逆波兰表达式。...
  • 表达式2*(9+6/3-5)+4,称为中缀表达式,表示成2 9 6 3 / + 5 - * 4 +称为后缀表达式,表示成+ * 2 - + 9 / 6 3 5 4称为前缀表达式。 ·基本要求 将中缀表达式,转换为后缀表达式和前缀表达式,再分别计算转换后的...
  • 相对应的符号在操作数后面的就叫后缀表达式(也称逆波兰式),符号在操作数前面的就叫前缀表达式(也称波兰式)。 为什么要把中缀表达式转化为后缀,前缀? 计算机没法计算带有括号,以及区分优先级的表达式,或者...
  • 这里再做一个前缀表达式的总结: 初始化两个栈:运算符栈S1和储存中间结果的栈S2; 从右至左扫描中缀表达式; 遇到操作数时,将其压入S2; 遇到运算符时,比较其与S1栈顶运算符的优先级: 4.1 如果S1为空或栈顶...
  • 这是一个循环♻️过程 4)辅助栈的指针前移一位(这是因为当前指在右括号), 5)若扫描完表达式之后,辅助栈还有元素,全部出栈,入到结果栈 此时,将中间结果栈的元素全部出栈,得到的就是前缀表达式
  • 前缀表达式/中缀表达式/后缀表达式 中缀表达式就是平常的表达式,如(3+4)*5-6=29 前缀表达式又称为波兰式,也就是运算符位于数字前面,如 -*+3456 后缀表达式又称为逆波兰式,也就是运算符位于数字后面,如 3 4 + 5...
  • 简单的前缀表达式计算 简单是指表达式简单,所有数字均为 0~9 之间,不是代码简单 【关于二叉树的递归创建与非递归遍历】 【其他:中缀表达式转后缀表达式】 【其他:后缀表达式计算】 思路 因为给定的是前缀表达式...
  • 前缀表达式中缀表达式后缀表达式之间的转换一、前缀表达式二、使用步骤1.引入库2.读入数据总结 代码实现的工具类ExpressionUtils,类中有两个静态方法,calculateResult方法是实现两数的加减乘除操作,getPriority方法...
  • 数据结构正好学到栈,中缀,前缀,后缀表达式把人绕的不行,写一个博客也算是总结一下这5个算法:中缀表达式的计算,中缀表达式转后缀表达式,后缀表达式计算,中缀表达式转前缀表达式前缀表达式计算 中缀表达式的...
  • 1、前缀表达式和后缀表达式的形成 2、前缀表达式和后缀表达式在计算机中如何计算。 中缀表达式就是我们数学中常用的那种表达式,本文打算以中缀表达式:1 + (2 + 3) × 4 - 5 为例,分享一下前缀表达式和后缀...
  • 前缀表达式的值

    万次阅读 多人点赞 2018-05-25 21:08:57
    7-1 求前缀表达式的值(20 分)算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前,例如2+3*(7-4)+8/4的前缀表达式是:+ + 2 * 3 - 7 4 / 8 4。请设计程序计算...
  • 本文主要介绍中缀表达式转前缀表达式算法和代码实现
  • 1 前缀表达式介绍 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前举例说明: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 1.1 前缀表达式的计算机求值过程 从右至左扫描表达式,遇到数字时,将...
  • 仿照后缀表达式的计算过程,把用字符数组来保存计算结果。 【代码】 #include <stdio.h> #include <stdlib.h> #include <string.h> #define maxSize 100 typedef struct BTNode { char data;...
  • 关于前缀表达式

    2018-11-26 19:46:26
    前缀表达式 例如((34+22) - (24/11) * 12) * 3.5 / (23 * 12/11) 写成前缀表达式就是 / * - + 34 22 * / 24 11 12 3.5 * 23 / 12 11 前缀表达式的运算法则就是如果读取的是一个运算符号,就向下寻找两个数据进行运算...
  • 中缀表达式转前缀表达式 c++

    千次阅读 2018-08-15 15:50:44
    输入表达式,输出相应二叉树的前序遍历结果 例如输入:a+b*(c-d)-e/f  输出:-+a*b-cd/ef  用两个栈实现, (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2; (2) 从右至左扫描中缀表达式; (3) 遇到操作数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 155,057
精华内容 62,022
关键字:

如何前缀表达式