精华内容
下载资源
问答
  • 有趣的数据结构算法10——利用栈计算后缀表达式的结果解题思路实现代码GITHUB下载连接 在前一天已经利用栈完成2进制到8进制的转换。但是栈的应用方面还有很多,本次我将讲解如何计算后缀表达式的结果。 解题思路 ...

    有趣的数据结构算法10——后缀表达式(PRN)介绍及利用栈计算后缀表达式的结果

    在前一天已经利用栈完成2进制到8进制的转换。但是栈的应用方面还有很多,本次我将讲解如何计算后缀表达式的结果。
    在这里插入图片描述

    解题思路

    后缀表达式(PRN)也叫逆波兰表达式,是在计算机中用于求值的一种方式,其求值过程可以用到栈来辅助存储。
    在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称为中缀表示,如1+2。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法,按此方法,每一运算符都置于其运算对象之后,故称为后缀表示,如12+。
    它的优势在于只用两种简单操作,入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下:
    如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。
    中缀表达式转换到后缀表达式公式
    假定待求值的后缀表达式为:1 2 + 5 3 6 + * + 7 - ,其实际上为1+2+5*(3+6)-7。其求值过程如下:
    1、遍历表达式,遇到1和2,压入栈中。此时栈如图所示:

    示例1
    2、接着读到+号,弹出2与1,执行加法运算,得到3,再次入栈。此时栈如图所示:

    示例2
    3、遇到5、3和6,压入栈中。此时栈如图所示:

    示例3
    4、接着读到+号,弹出6与3,执行加法运算,得到9,再次入栈。此时栈如图所示:

    示例4
    5、接着读到*号,弹出9与5,执行加法运算,得到45,再次入栈。此时栈如图所示:

    示例5
    6、接着读到+号,弹出45与3,执行加法运算,得到48,再次入栈。此时栈如图所示:

    示例6
    7、遇到7,压入栈中。此时栈如图所示:

    示例7
    8、接着读到-号,弹出7与48,执行加法运算,得到41,再次入栈。
    9、由于表达式已结束,读出栈内的最后一个元素,就是结果41。

    实现代码

    #include <stdio.h>
    #include <stdlib.h>
    #define Maxsize 10
    typedef double Ele;
    
    struct stack
    {
    	Ele* top;
    	Ele* bottom;
    	int stacksize;
    };
    
    typedef struct stack* Stack;
    
    void init(Stack s){			//初始化栈
    	Ele *p;
    	p = (Ele*)malloc(Maxsize * sizeof(Ele));
    	if (p == NULL){
    		printf("error");
    		exit(1);
    	}
    	s->top = s->bottom = p;
    	s->stacksize = Maxsize;
    }
    
    void PUSH(Stack s, Ele data){		//入栈
    	int length;
    	length = s->top - s->bottom;
    	if (length >= s->stacksize){
    		s->bottom = (Ele*)realloc(s->bottom,(s->stacksize + Maxsize) * sizeof(Ele));
    		if (s->bottom == NULL){
    			printf("内存分配失败\n");
    			exit(1);
    		}
    		s->stacksize = s->stacksize + Maxsize;//更新stacksize的值
    		s->top = s->bottom + length; //更新top的值
    	}
    	*(s->top) = data;
    	s->top++;
    }
    Ele POP(Stack s){					//出栈
    	Ele num;
    	if (s->top == s->bottom){
    		printf("栈内没有元素了!\n");
    		exit(1);
    	}
    	s->top--;
    	num = *(s->top);
    	return num;
    }
    
    int main(){
    	struct stack s;			//定义栈
    	char c = 0,str[10];		//c用于从键盘获取字符,str用于存储每一轮输入的数字,之后会转化成double类型
    	Ele a1, a2, num;		//a1,a2用于栈的运算
    	int i = 0;				//temp量
    
    
    	init(&s);				//初始化栈
    	printf("请输入一个算式:");		
    
    	scanf("%c", &c);		//输入一个字符
    	while (c != '#')
    	{
    		while ((c <= '9' && c >= '0') || c == '.'){	//该部分用于获取一个double类型的数字
    			str[i++] = c;
    			str[i] = '\0';
    			if (i >= 10){
    				printf("输入数据过大");
    				exit(1);
    			}
    			scanf("%c", &c);
    			if (!(c <= '9' && c >= '0') && !(c == '.')){
    				a1 = atof(str);						//该函数用于将字符串转化位double
    				PUSH(&s, a1);
    				i = 0;
    				break;
    			}
    		}
    		switch (c)								//判断是否属于加减乘除
    		{
    		case '+': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 + a1);
    			break;
    		case '-': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 - a1);
    			break;
    		case '*': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 * a1);
    			break;
    		case '/': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 / a1);
    			break;
    		case ' ':
    			break;
    		case '#':
    			break;
    		default:
    			printf("输入符号错误!\n");
    			break;
    		}
    		scanf("%c", &c);
    	}
    	num = POP(&s);
    	printf("%.3f\n", num);
    
    	return 0;
    }
    

    GITHUB下载连接

    https://github.com/bubbliiiing/Data-Structure-and-Algorithm

    希望得到朋友们的喜欢。
    有问题的朋友可以提问噢。

    展开全文
  • 前言假如要你实现一个可以识别表达式的简易计算器,你会怎么实现?例如用户输入:3 + 5 * (2 - 4) ...后缀表达式而对于计算机来说,实际也可以采用类似的顺序,先记录存储3为a,然后存储5为b,计算2...

    前言

    假如要你实现一个可以识别表达式的简易计算器,你会怎么实现?例如用户输入:

    3 + 5 * (2 - 4)
    

    可以直接得出计算结果:-7。对于人类来说,我们很容易计算出来,因为我们从左往右看,看到后面括号时,知道括号内的计算优先级最高,因此可以先计算括号内的,然后反过来计算乘法,最后计算加法,得到最终结果。

    后缀表达式

    而对于计算机来说,实际也可以采用类似的顺序,先记录存储3为a,然后存储5为b,计算2-4结果存入c,再然后计算b*c存储d,最终计算a+d得到最终结果。而这种计算过程的操作顺序可描述如下(把操作符号放在操作数后面):

    3 5 2 4 - * +
    

    这种记法叫做后缀或逆波兰记法(而我们平常见到的叫中缀记法),它的特点是不需要用括号就能表示出整个表达式哪部分运算先进行,也就是说不需要考虑优先级,这非常符合计算机的处理方式。这种记法很容易使用我们前面介绍的栈来求值,但是前提是需要将中缀表达式先转换为后缀表达式。对于这种转换,我们也可以使用前面介绍的栈-C语言实现或者将要介绍的树来完成,因篇幅有限,本文不准备介绍。

    接下来将会介绍如何利用中缀表达式进行求值。

    利用栈实现中缀表达式求值

    前面也说到,所谓中缀表达式,就是我们能看到的正常表达式,中缀表达式求值,也就是直接对输入的表达式进行求值。为简单起见,我们这里假设只涉及加减乘除和小括号,并且操作数都是正整数,不涉及更加复杂的数据或运算。

    计算思路:

    • 使用两个栈,stack0用于存储操作数,stack1用于存储操作符
    • 从左往右扫描,遇到操作数入栈stack0
    • 遇到操作符时,如果优先级低于或等于栈顶操作符优先级,则从stack0弹出两个元素进行计算,并压入stack0,继续与栈顶操作符的比较优先级
    • 如果遇到操作符高于栈顶操作符优先级,则直接入栈stack1
    • 遇到左括号,直接入栈stack1,遇到右括号,则直接出栈并计算,直到遇到左括号

    上面的思路可能看起来不是很明确,我们举一个简单的例子,假如要对下面的表达式求值:

    6 * (2 + 3 )* 8 + 5
    

    我们从左往右开始扫描。首先遇到操作数‘6’,和操作符‘*’,分别入栈
    stack0:

    栈顶6

    stack1:

    栈顶*

    继续往后扫描,遇到‘(’直接入栈,‘2’入栈,栈顶是左括号,’+‘入栈,‘3’入栈
    stack0:

    栈顶623

    stack1:

    栈顶*(+

    继续往后扫描,遇到右括号,它与栈顶操作符‘+’相比,优先级要高,因此,将‘+’出栈,弹出两个操作数‘3’,‘2’,计算结果得到‘5’,并入栈:

    stack0:

    栈顶65

    stack1:

    栈顶*(

    继续出栈,直到遇到左括号
    stack0:

    栈顶65

    stack1:

    栈顶*

    继续往后扫描,遇到操作符‘’,优先级与栈顶‘’优先级相同,因此弹出操作数并计算得到30入栈,最后‘*’入栈

    stack0:

    栈顶30

    stack1:

    栈顶*

    继续扫描,‘8’入栈,操作符‘+’优先级小于‘*’,弹出操作数计算得到结果‘240’,并将其入栈,最后‘+’也入栈

    stack0:

    栈顶240

    stack1:

    栈顶+

    最后‘5’入栈,发现操作符栈不为空,弹出操作符‘+’和两个操作数,并进行计算,得到‘245’,入栈,得到最终结果。
    stack0

    栈顶245

    stack1:

    代码实现

    #include<stdio.h>
    #include<ctype.h>
    #define STACK_SIZE 64 /*栈大小*/
    #define TOP_OF_STACK -1 /*栈顶位置*/
    typedef int ElementType; /*栈元素类型*/
    
    #define SUCCESS 0
    #define FAILURE -1
    
    /*定义栈结构*/
    typedef struct StackInfo
    {
        int topOfStack; /*记录栈顶位置*/
        ElementType stack[STACK_SIZE]; /*栈数组,也可以使用动态数组实现*/
    }StackInfo_st;
    
    
    /*函数声明*/
    int stack_push(StackInfo_st *s,ElementType value);
    int stack_pop(StackInfo_st *s,ElementType *value);
    int stack_top(StackInfo_st *s,ElementType *value);
    int stack_is_full(StackInfo_st *s);
    int stack_is_empty(StackInfo_st *s);
    
    
    /*入栈,0表示成,非0表示出错*/
    int stack_push(StackInfo_st *s,ElementType value)
    {
        if(stack_is_full(s))
            return FAILURE;
        /*先增加topOfStack,再赋值*/
        s->topOfStack++;
        s->stack[s->topOfStack] = value;
        return SUCCESS;
    }
    
    /*出栈*/
    int stack_pop(StackInfo_st *s,ElementType *value)
    {
     /*首先判断栈是否为空*/
        if(stack_is_empty(s))
            return FAILURE;
        *value = s->stack[s->topOfStack];
        s->topOfStack--;
        return SUCCESS;
    }
    /*访问栈顶元素*/
    int stack_top(StackInfo_st *s,ElementType *value)
    {
        /*首先判断栈是否为空*/
        if(stack_is_empty(s))
        {
            printf("stack is empty");
                return FAILURE;
        }
        *value = s->stack[s->topOfStack];
        return SUCCESS;
    }
    
    /*判断栈是否已满,满返回1,未满返回0*/
    int stack_is_full(StackInfo_st *s)
    {
        return s->topOfStack == STACK_SIZE - 1;
    }
    /*判断栈是否为空,空返回1,非空返回0*/
    int stack_is_empty(StackInfo_st *s)
    {
        return s->topOfStack == - 1;
    }
    
    /*用于记录符号的优先级,这里浪费了一些内存,可以优化*/
    static char priority[128] = {0};
    void priorityInit()
    {
        /*初始化优先级,值越小,优先级越高*/
        priority['+'] = 4;
        priority['-'] = 4;
        priority['*'] = 3;
        priority['/'] = 3;
        priority['('] = 1;
        priority[')'] = 1;
    
    
    }
    /*比较运算符的优先级,op1优先级大于op2时,返回大于0的值*/
    int priorityCompare(char op1,char op2)
    {
        return priority[op2] - priority[op1];
    }
    /*出栈操作符和操作数进行计算*/
    int calcOp(StackInfo_st *nums,StackInfo_st *ops,int nowOp)
    {
        int a ,b,op;
        stack_pop(ops,&op);
        printf("op %c is <= %cn",nowOp,op);
        printf("get op from stack %cn",op);
        if(SUCCESS != stack_pop(nums,&b))
        {
            printf("pop failedn");
            return -1;
        }
        if(SUCCESS != stack_pop(nums,&a))
        {
            printf("pop failedn");
            return 0;
        }
        printf("get b from stack %dn",b);
    
        printf("get a from stack %dn",a);
        switch(op)
        {
            case '+':
            {
                printf("push %d into stackn",a+b);
                stack_push(nums,a+b);
                break;
            }
            case '-':
            {
                stack_push(nums,a-b);
                break;
            }
            case '*':
            {
                printf("push %d into stackn",a*b);
                stack_push(nums,a*b);
                break;
            }
            case '/':
            {
                printf("push %d into stackn",a/b);
                stack_push(nums,a/b);
                break;
            }
        }
        return 1;
    }
    int calc(const char* exp,int *result)
    {
        if(NULL == exp || NULL == result)
            return FAILURE;
        /*创建栈,用于保存数*/
        StackInfo_st nums;
        nums.topOfStack = TOP_OF_STACK;
    
        /*用于保存操作符*/
        StackInfo_st ops;
        ops.topOfStack = TOP_OF_STACK;
        int index = 0;
        /*用于标记,判断上一个是否为数字*/
        int flag = 0;
        int temp = 0;
        int op ;
        while(0 != *exp)
        {   
            /*如果是数字*/
            if(isdigit(*exp))
            {
                printf("char is %cn",*exp);
                 /*如果上一个还是数字,则取出栈顶数据*/
                if(1 == flag)
                   {
    
                    stack_pop(&nums,&temp);
                    printf("pop from stack num %dn",temp);
                    }
                else
                    temp = 0;
                flag = 1;
                temp = 10 * temp + *exp-'0';
                printf("push %d to stackn",temp);
                stack_push(&nums,temp);
            }
            /*如果是操作符*/
            else if('/' == *exp || '*' == *exp || '+' == *exp || '-' == *exp)
            {
                flag = 0;
                printf("OP is %cn",*exp);
                while((ops.topOfStack > TOP_OF_STACK )&&(SUCCESS == stack_top(&ops,&op))&&'(' != op && ')'!=op&&(priorityCompare(*exp,op) < 0))
                {
                    calcOp(&nums, &ops,*exp);
                }
                printf("push %c to stack opsn",*exp);
                stack_push(&ops,*exp);
            }
            /*左括号直接入栈*/
            else if('(' == *exp )
            {
                printf("push ( to stack opsn");
                flag = 0;
                stack_push(&ops,*exp);
            }
            /*右括号,计算*/
            else if(')' ==*exp )
            {
                printf("deal with  ) in opsn");
                flag = 0;
                /*右括号时,不断计算,直到遇见左括号*/
                while(SUCCESS == stack_top(&ops,&op) && '(' != op)
                {
                    calcOp(&nums, &ops,*exp);
                }
                stack_pop(&ops,&op);
            }
            else
            {
                flag=0;
            }
            printf("flag is %dnn",flag);
            exp++;
        }
        /*计算剩余两个栈的内容*/
        while((!stack_is_empty(&ops)) && (!stack_is_empty(&nums)))
        {
            if(!calcOp(&nums, &ops,0))
            printf("exp is errorn");
        }
        stack_pop(&nums,&temp);
        /*如果栈中还有内容,说明表达式错误*/
        if((!stack_is_empty(&ops)) || (!stack_is_empty(&nums)))
            printf("nnexp is oknn");
    
        if(SUCCESS == stack_pop(&nums,&temp))
            printf("result is %dn",temp);
        *result = temp;
        return 0;
    }
    int main(int argc ,char *argv[])
    {
    
        int result;
        priorityInit();
        char exp[] = "6 * (2 + 3 * 3)* 8 + 5";
        calc(exp,&result);
        printf("result is %dn",result);
        return 0;
    }
    

    总结

    本文介绍了利用栈对中缀表达式进行求值,而代码实现还有很多不足之处,例如对表达式的正确性校验不足,只能处理正整数等等,欢迎在此基础上完善补充。尽管如此,整个过程对使用栈进行中缀表达式的求值做了一个较为完整的介绍,因此具有一定的参考性。

    微信公众号【编程珠玑】:专注但不限于分享计算机编程基础,Linux,C语言,C++,数据结构与算法,工具,资源等编程相关[原创]技术文章,号内包含大量经典电子书和视频学习资源。欢迎一起交流学习,一起修炼计算机“内功”,知其然,更知其所以然。

    5fec018516d6c3b7e3ad6f77914e5e88.png
    展开全文
  • 前言假如要你实现一个可以识别表达式的简易计算器,你会怎么实现?例如用户输入:3+5*(2-4)可以直接得出计算结果:-7。...后缀表达式而对于计算机来说,实际也可以采用类似的顺序,先记录存储3为a,然后存储5为b...

    前言

    假如要你实现一个可以识别表达式的简易计算器,你会怎么实现?例如用户输入:

    3 + 5 * (2 - 4)

    可以直接得出计算结果:-7。对于人类来说,我们很容易计算出来,因为我们从左往右看,看到后面括号时,知道括号内的计算优先级最高,因此可以先计算括号内的,然后反过来计算乘法,最后计算加法,得到最终结果。

    后缀表达式

    而对于计算机来说,实际也可以采用类似的顺序,先记录存储3为a,然后存储5为b,计算2-4结果存入c,再然后计算b*c存储d,最终计算a+d得到最终结果。而这种计算过程的操作顺序可描述如下(把操作符号放在操作数后面):

    3 5 2 4 - * +

    这种记法叫做后缀或逆波兰记法(而我们平常见到的叫中缀记法),它的特点是不需要用括号就能表示出整个表达式哪部分运算先进行,也就是说不需要考虑优先级,这非常符合计算机的处理方式。这种记法很容易使用我们前面介绍的栈来求值,但是前提是需要将中缀表达式先转换为后缀表达式。对于这种转换,我们也可以使用前面介绍的《栈-C语言实现》或者将要介绍的树来完成,因篇幅有限,本文不准备介绍。

    接下来将会介绍如何利用中缀表达式进行求值。

    利用栈实现中缀表达式求值

    前面也说到,所谓中缀表达式,就是我们能看到的正常表达式,中缀表达式求值,也就是直接对输入的表达式进行求值。为简单起见,我们这里假设只涉及加减乘除和小括号,并且操作数都是正整数,不涉及更加复杂的数据或运算。

    计算思路:

    • 使用两个栈,stack0用于存储操作数,stack1用于存储操作符

    • 从左往右扫描,遇到操作数入栈stack0

    • 遇到操作符时,如果优先级低于或等于栈顶操作符优先级,则从stack0弹出两个元素进行计算,并压入stack0,继续与栈顶操作符的比较优先级

    • 如果遇到操作符高于栈顶操作符优先级,则直接入栈stack1

    • 遇到左括号,直接入栈stack1,遇到右括号,则直接出栈并计算,直到遇到左括号

    上面的思路可能看起来不是很明确,我们举一个简单的例子,假如要对下面的表达式求值:

    * (2 + 3 )* 8 + 5

    我们从左往右开始扫描。首先遇到操作数‘6’,和操作符‘*’,分别入栈
    stack0:

    栈顶
    6

    stack1:

    栈顶
    *

    继续往后扫描,遇到‘(’直接入栈,‘2’入栈,栈顶是左括号,’+‘入栈,‘3’入栈
    stack0:

    栈顶
    623

    stack1:

    栈顶
    *(+

    继续往后扫描,遇到右括号,它与栈顶操作符‘+’相比,优先级要高,因此,将‘+’出栈,弹出两个操作数‘3’,‘2’,计算结果得到‘5’,并入栈:

    stack0:

    栈顶
    65

    stack1:

    栈顶
    *(

    继续出栈,直到遇到左括号
    stack0:

    栈顶
    65

    stack1:

    栈顶
    *

    继续往后扫描,遇到操作符‘’,优先级与栈顶‘’优先级相同,因此弹出操作数并计算得到30入栈,最后‘*’入栈

    stack0:

    栈顶
    30

    stack1:

    栈顶
    *

    继续扫描,‘8’入栈,操作符‘+’优先级小于‘*’,弹出操作数计算得到结果‘240’,并将其入栈,最后‘+’也入栈

    stack0:

    栈顶
    240

    stack1:

    栈顶
    +

    最后‘5’入栈,发现操作符栈不为空,弹出操作符‘+’和两个操作数,并进行计算,得到‘245’,入栈,得到最终结果。

    stack0:

    栈顶
    245

    stack1:

    代码实现

    以下为关键部分代码,完整可运行代码可阅读原文进行查看或访问
    https://www.yanbinghu.com/2019/03/24/57779.html

    /*用于记录符号的优先级,这里浪费了一些内存,可以优化*/
    static char priority[128] = {0};
    void priorityInit(){
        /*初始化优先级,值越小,优先级越高*/
        priority['+'] = 4;
        priority['-'] = 4;
        priority['*'] = 3;
        priority['/'] = 3;
        priority['('] = 1;
        priority[')'] = 1;


    }
    /*比较运算符的优先级,op1优先级大于op2时,返回大于0的值*/
    int priorityCompare(char op1,char op2){
        return priority[op2] - priority[op1];
    }
    /*出栈操作符和操作数进行计算*/
    int calcOp(StackInfo_st *nums,StackInfo_st *ops,int nowOp){
        int a ,b,op;
        stack_pop(ops,&op);
        printf("op %c is <= %c\n",nowOp,op);
        printf("get op from stack %c\n",op);
        if(SUCCESS != stack_pop(nums,&b))
        {
            printf("pop failed\n");
            return -1;
        }
        if(SUCCESS != stack_pop(nums,&a))
        {
            printf("pop failed\n");
            return 0;
        }
        printf("get b from stack %d\n",b);

        printf("get a from stack %d\n",a);
        switch(op)
        {
            case '+':
            {
                printf("push %d into stack\n",a+b);
                stack_push(nums,a+b);
                break;
            }
            case '-':
            {
                stack_push(nums,a-b);
                break;
            }
            case '*':
            {
                printf("push %d into stack\n",a*b);
                stack_push(nums,a*b);
                break;
            }
            case '/':
            {
                printf("push %d into stack\n",a/b);
                stack_push(nums,a/b);
                break;
            }
        }
        return 1;
    }
    int calc(const charexp,int *result){
        if(NULL == exp || NULL == result)
            return FAILURE;
        /*创建栈,用于保存数*/
        StackInfo_st nums;
        nums.topOfStack = TOP_OF_STACK;

        /*用于保存操作符*/
        StackInfo_st ops;
        ops.topOfStack = TOP_OF_STACK;
        int index = 0;
        /*用于标记,判断上一个是否为数字*/
        int flag = 0;
        int temp = 0;
        int op ;
        while(0 != *exp)
        {   
            /*如果是数字*/
            if(isdigit(*exp))
            {
                printf("char is %c\n",*exp);
                 /*如果上一个还是数字,则取出栈顶数据*/
                if(1 == flag)
                {

                    stack_pop(&nums,&temp);
                    printf("pop from stack num %d\n",temp);
                }
                else
                    temp = 0;
                flag = 1;
                temp = 10 * temp + *exp-'0';
                printf("push %d to stack\n",temp);
                stack_push(&nums,temp);
            }
            /*如果是操作符*/
            else if('/' == *exp || '*' == *exp || '+' == *exp || '-' == *exp)
            {
                flag = 0;
                printf("OP is %c\n",*exp);
                while((ops.topOfStack > TOP_OF_STACK )&&(SUCCESS == stack_top(&ops,&op))&&'(' != op && ')'!=op&&(priorityCompare(*exp,op) 0))
                {
                    calcOp(&nums, &ops,*exp);
                }
                printf("push %c to stack ops\n",*exp);
                stack_push(&ops,*exp);
            }
            /*左括号直接入栈*/
            else if('(' == *exp )
            {
                printf("push ( to stack ops\n");
                flag = 0;
                stack_push(&ops,*exp);
            }
            /*右括号,计算*/
            else if(')' ==*exp )
            {
                printf("deal with  ) in ops\n");
                flag = 0;
                /*右括号时,不断计算,直到遇见左括号*/
                while(SUCCESS == stack_top(&ops,&op) && '(' != op)
                {
                    calcOp(&nums, &ops,*exp);
                }
                stack_pop(&ops,&op);
            }
            else
            {
                flag=0;
            }
            printf("flag is %d\n\n",flag);
            exp++;
        }
        /*计算剩余两个栈的内容*/
        while((!stack_is_empty(&ops)) && (!stack_is_empty(&nums)))
        {
            if(!calcOp(&nums, &ops,0))
            printf("exp is error\n");
        }
        stack_pop(&nums,&temp);
        /*如果栈中还有内容,说明表达式错误*/
        if((!stack_is_empty(&ops)) || (!stack_is_empty(&nums)))
            printf("\n\nexp is ok\n\n");

        if(SUCCESS == stack_pop(&nums,&temp))
            printf("result is %d\n",temp);
        *result = temp;
        return 0;
    }

    总结

    本文介绍了利用栈对中缀表达式进行求值,而代码实现还有很多不足之处,例如对表达式的正确性校验不足,只能处理正整数等等,欢迎在此基础上完善补充。尽管如此,整个过程对使用栈进行中缀表达式的求值做了一个较为完整的介绍,因此具有一定的参考性。

    推荐阅读:

    leetcode题解-20.有效的括号

    如何自己实现一个栈

    关注公众号【编程珠玑】,获取更多Linux/C/C++/Python/Go/算法/工具等原创技术文章。后台免费获取经典电子书和视频资源。

    22143ae9f4e2d9fdd4bdd86b69e7b85d.png

    展开全文
  • 大佬们,如何利用栈实现实数(带小数点,位数不限)的后缀表达式求值?
  • 上次介绍如何利用栈实现中缀表达式值,如果我是出题官,当然要考前缀,后缀,中缀表达式相互转换,然后就变成了利用栈实现前缀和后缀表达式求值。前缀,后缀,中缀表达式相互转换及其运算,可以说是计算机考研的一...

    f3bbd69c3baa20f323be743a8466b649.png

    「@Author:Runsen」

    编程的本质来源于算法,而算法的本质来源于数学,编程只不过将数学题进行代码化。「---- Runsen」

    算法,一门既不容易入门,也不容易精通的学问。

    上次介绍如何利用栈实现中缀表达式求值,如果我是出题官,当然要考前缀,后缀,中缀表达式相互转换,然后就变成了利用栈实现前缀和后缀表达式求值。

    前缀,后缀,中缀表达式相互转换及其运算,可以说是计算机考研的一个重点。

    首先看下面所示表格:

    中序表达式2*3/(2-1)+3*(4-1)
    前序表达式+/*23-21*3-41
    后序表达式23*21-/341-*+

    注意:前序表达式和后序表达式是没有扩号

    这篇文章有对应的图解:https://mp.weixin.qq.com/s/NRbFXZAXEUeXhKKYY7CReg

    中缀表达式转前缀表达式求值

    中缀表达式转前缀表达式的规则:

    1、反转输入字符串,如“2*3/(2-1)+3*(4-1)” 反转后为“ )1-4(*3+)1-2(/3*2”,
    2、从字符串中取出下一个字符
      2.1.如果是操作数,直接输出
      2.2.如果是“)”,压入栈中
      2.3.如果是运算符但不是“(”,“)”,则不断循环进行以下处理
        2.3.1.如果栈为空,则此运算符进栈,结束此步骤
        2.3.2.如果栈顶是“)”,则此运算符进栈,结束此步骤
        2.3.2.如果此运算符与栈顶优先级相同或者更高,此运算符进栈,结束此步骤
        2.3.4.否则,运算符连续出栈,直到满足上述三个条件之一,然后此运算符进栈
      2.4、如果是“(”,则运算符连续出栈,直到遇见“)”为止,将“)”出栈且丢弃之
    3、如果还有更多的字符串,则转到第2步
    4、不在有未处理的字符串了,输出栈中剩余元素
    5、再次反转字符串得到最终结果

    经过上面的步骤,得到的输出既是转换得到的前缀表达式。

    前缀表达式的计算方法:对前缀表达式从后向前扫描,设定一个操作数栈,如果是操作数,则将其直接入栈,如果是操作符,则从栈中弹出操作符对应的操作数进行运算,并将计算结果压栈。直至从右到左扫描完毕整个前缀表达式,这时操作数栈中应该只有一个元素,该元素的值则为前缀表达式的计算结果。

    上面的过程使用数据结构栈来实现,具体代码如下

    '''
    @Author:Runsen
    @WeChat:RunsenLiu
    @微信公众号:Python之王
    @CSDN:https://blog.csdn.net/weixin_44510615
    @Github:https://github.com/MaoliRUNsen
    @Date:2020/12/17
    '''

    import re

    class Stack():
        def __init__(self):
            self.items = []

        def push(self, item):
            return self.items.append(item)

        def pop(self):
            return self.items.pop()

        def size(self):
            return len(self.items)

        def peek(self):
            return self.items[len(self.items) - 1]

        def display(self):
            print(self.items)

    def infix_to_prefix(s):
        prec = {
            '*'3,
            '/'3,
            '+'2,
            '-'2,
            '('4,
            ')'1
        }

        a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('请输入中缀表达式:'))
        prefix = []

        for x in a[::-1]:
            if re.match('[0-9]', x):
                #操作数,直接输出
                prefix.append(x)
            else:
                #如果是“)”,压入栈中
                if x == ')':
                    s.push(x)
                elif x == '(':
                    while True:
                        i = s.pop()
                        if i == ')':
                            break
                        else:
                            prefix.append(i)
                else:
                    if s.size() > 0 and prec[x] <= prec[s.peek()]:
                        prefix.append(s.pop())
                    s.push(x)
        for _ in range(s.size()):
            prefix.append(s.pop())
        return prefix[::-1]
        
    def cal_prefix(s, prefix):
        # 思路:对前缀表达式从后向前扫描,设定一个操作数栈,如果是操作数,则将其直接入栈,如果是操作符,则从栈中弹出操作符对应的操作数进行运算,并将计算结果压栈。
        # 直至从右到左扫描完毕整个前缀表达式,这时操作数栈中应该只有一个元素,该元素的值则为前缀表达式的计算结果。
        for x in prefix[::-1]:
            if re.match('[0-9]', x):
                s.push(x)
            else:
                a2 = int(s.pop())
                a1 = int(s.pop())
                if x == '*':
                    a = a1 * a2
                elif x == '/':
                    a = a2 / a1
                elif x == '+':
                    a = a1 + a2
                else:
                    a = a2 - a1
                s.push(a)
        return s.pop()

    if __name__ == '__main__':
        s = Stack()
        prefix = infix_to_prefix(s)
        print('前缀表达式:', prefix)
        prefix_val = cal_prefix(s, prefix)
        print('前缀表达式计算结果:', prefix_val)

    请输入中缀表达式:2*3/(2-1)+3*(4-1)
    前缀表达式: ['+''*''2''/''3''-''2''1''*''3''-''4''1']
    前缀表达式计算结果: 15
    请输入中缀表达式:9+(3-1*2)*3+10/2
    前缀表达式: ['+''+''9''*''-''3''*''1''2''3''/''10''2']
    前缀表达式计算结果: 17

    中缀表达式转换为后缀表达式求值

    中缀表达式转后缀表达式的规则:

    1.遇到操作数,直接输出;

    2.栈为空时,遇到运算符,入栈;

    3.遇到左括号,将其入栈;

    4.遇到右括号,执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出;

    5.遇到其他运算符’+”-”*”/’时,弹出所有优先级大于或等于该运算符的栈顶元素,然后将该运算符入栈;

    6.最终将栈中的元素依次出栈,输出。

    经过上面的步骤,得到的输出既是转换得到的后缀表达式。

    后缀表达式的计算方法:对后缀表达式从前向后扫描,设定一个操作数栈,如果是操作数,则将其直接入栈,如果是操作符,则从栈中弹出操作符对应的操作数进行运算,并将计算结果压栈。直至从右到左扫描完毕整个后缀表达式,这时操作数栈中应该只有一个元素,该元素的值则为后缀表达式的计算结果。

    上面的过程使用数据结构栈来实现,具体代码如下

    '''
    @Author:Runsen
    @WeChat:RunsenLiu
    @微信公众号:Python之王
    @CSDN:https://blog.csdn.net/weixin_44510615
    @Github:https://github.com/MaoliRUNsen
    @Date:2020/12/17
    '''

    import re

    class Stack():
        def __init__(self):
            self.items = []

        def push(self, item):
            return self.items.append(item)

        def pop(self):
            return self.items.pop()

        def size(self):
            return len(self.items)

        def peek(self):
            return self.items[len(self.items) - 1]

        def display(self):
            print(self.items)


    def infix_to_postfix (s):
        prec = {
            '*'3,
            '/'3,
            '+'2,
            '-'2,
            '('1,
            ')'4
        }

        a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('请输入中缀表达式:'))
        postfix = []

        for x in a:
            if re.match('[0-9]', x):
                # 操作数,直接输出
                postfix.append(x)
            else:
                # 如果是“(”,压入栈中
                if x == '(':
                    s.push(x)
                elif x == ')':
                    while True:
                        i = s.pop()
                        if i == '(':
                            break
                        else:
                            postfix.append(i)
                else:
                    if s.size() > 0 and prec[x] <= prec[s.peek()]:
                        postfix.append(s.pop())
                    s.push(x)
        for _ in range(s.size()):
            postfix.append(s.pop())
        return postfix


    def cal_postfix (s, postfix):
        for x in postfix:
            if re.match('[0-9]', x):
                s.push(x)
            else:
                a1 = int(s.pop())
                a2 = int(s.pop())
                if x == '*':
                    a = a1 * a2
                elif x == '/':
                    a = a2 / a1
                elif x == '+':
                    a = a1 + a2
                else:
                    a = a2 - a1
                s.push(a)
        return s.pop()


    if __name__ == '__main__':
        s = Stack()
        postfix = infix_to_postfix(s)
        print('后缀表达式:', postfix)
        postfix_val = cal_postfix (s, postfix)
        print('后缀表达式计算结果:', postfix_val)


    请输入中缀表达式:2*3/(2-1)+3*(4-1)
    ['2''3''*''2''1''-''/''3''4''1''-']
    后缀表达式: ['2''3''*''2''1''-''/''3''4''1''-''*''+']
    后缀表达式计算结果: 15
    请输入中缀表达式:9+(3-1*2)*3+10/2
    后缀表达式: ['9''3''1''2''*''-''3''*''10''2''/''+''+']
    后缀表达式计算结果: 17

    其实此题是Leetcode第150题,逆波兰表达式求值。

    根据 逆波兰表示法,求表达式的值。

    有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

    示例 1:

    输入: ["2""1""+""3""*"]
    输出: 9
    解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
    示例 2:

    输入: ["4""13""5""/""+"]
    输出: 6
    解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

    前缀表达式转中缀表达式

    从右往左开始,取出一个操作符和操作符右边的两个数进行计算,并将计算的结果放过去,直到计算结束。以前缀表达式+/*23-21*3-41为例,将其转换为中缀表达式:

    (1)取出-、4、1,计算并将结果放回得到+/*23-21*3(4-1)

    (2)取出*、3、(4-1),计算并将结果放回得到+/*23-21(3*(4-1))

    (3)取出-、2、1,计算并将结果放回得到+/*23(2-1)(3*(4-1))

    (3)取出*、2、3,计算并将结果放回得到+/(2*3)(2-1)(3*(4-1))

    (4)取出/、(2*3)、(2-1),计算并将结果放回得到+((2*3)/(2-1))(3*(4-1))

    (5)取出+、((2*3)/(2-1))、(3*(4-1)),计算将结果放回得到((2*3)/(2-1))+(3*(4-1)),计算结束,显然计算结果为15。

    后缀表达式转中缀表达式

    从左向右开始,取出一个操作符和操作符左边的两个数进行计算,并将计算的结果放过去,直到计算结束,以后缀表达式23*21-/341-*+为例,将其转换为中缀表达式:(1)取出2、3、*,计算并将结果放回得到(2*3)21-/341-*+

    (2)取出2,1,-,计算并将结果放回得到(2*3)(2-1)/341-*+

    (3)取出(2*3)(2-1)、/,计算并将结果放回得到((2*3)/(2-1))341-*+

    (4)取出4,1,-,计算并将结果放回得到((2*3)/(2-1)) 3(4-1)*+

    (5)取出3,(4-1),*,计算并将结果放回得到((2*3)/(2-1)) 3*(4-1)+

    (6)取出((2*3)/(2-1))3*(4-1)+,计算并将结果放回得到((2*3)/(2-1)) + 3*(4-1),显然计算结果为15。

    本文已收录 GitHub,传送门~[1] ,里面更有大厂面试完整考点,欢迎 Star。

    Reference

    [1]

    传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100

    更多的文章

    点击下面小程序

    27a11ce5f025bf66af079dca95a9d13c.png

    - END -

    59946250245c3ea1b36bd9768c0f9a52.png

    展开全文
  • 利用栈实现算术表达式的值,表达式中可包含加+、减(负) -、乘*、除/、 乘方^、括号( )运算符,操作数可以为浮点数。 可采用直接中缀表达式的方法, 也可采用先转换成后缀表达式后再值的方法(参看课件) 。 ...
  • 上次介绍如何利用栈实现中缀表达式值,如果我是出题官,当然要考前缀,后缀,中缀表达式相互转换,然后就变成了利用栈实现前缀和后缀表达式求值。前缀,后缀,中缀表达式相互转换及其运算,可以说是计算机考研的一...
  • 实验:利用栈求表达式值 利用栈实现算术表达式的求值,表达式中可包含加+、减(负)-、乘*、除/、乘方^、括号( )等运算符,操作数可以为浮点数。可采用直接求中缀表达式的方法,也可采用先转换成后缀表达式后再求值...
  • 中缀算术表达式求

    2012-07-04 02:10:35
    设计思路:从键盘输入中缀表达式,然后将中缀表达式转换为后缀表达式利用后缀表达式求值。要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式,利用给定的算术符优先关系,实现对算数四则混合运算...
  • 设计思路:从键盘输入中缀表达式,然后将中缀表达式转换为后缀表达式利用后缀表达式求值。要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式,利用给定的算术符优先关系,实现对算数四则混合运算...
  • 计算表达式

    2016-07-16 11:13:01
    看了紫书上的表达式树,上面讲用递归来建树,并给出了...讲的是如何利用栈四则运算表达式的值。但计算前需要将中缀表达式转为后缀表达式。 上面有基本的理论+详细的步骤,写的很不错。 以下是自己写的代码
  • 本篇简述如何将日常写的中缀表达式转化为后缀表达式,再进行值的一般流程。 【一】利用栈将中缀表达式转化为后缀表达式 基本过程: 从头到尾读取中缀表达式的每个对象,对不同的对象按不同的情况进行处理(注:...
  • 错误,循环队列指的是后者,用数组表示的队列,利用求余数运算使得头尾相接 4.在用数组表示的循环队列中,front值一定小于等于rear值F rear后裔 5.从一个栈顶指针为HS的链栈中删除一个结点时,用X保存被删结点的值,...
  • [TOC]一、什么是堆栈二、后缀表达式三、堆栈的抽象数据类型描述四、的顺序存储实现4.1 入栈4.2 出栈五、例:请用一个数组实现两个堆栈,要求最大地利用数组空间,使数组只要有空间入栈操作就可以成功。5.1 入栈5.2...
  • 它们与对应的二叉树结构相关,关于如何转化中缀表达式为前缀与后缀表达式本文不作详细介绍,请参阅《数据结构》与《编译原理》等相关教材。 这里我们通常选用后缀表达式作为中间临时输出,又称逆波兰表达式。但是,...
  • 大话数据结构

    2019-01-10 16:35:22
    4.9.3中缀表达式转后缀表达式 108 4.10队列的定义 111 电脑有时会处于疑似死机的状态。就当你失去耐心,打算了reset时。突然它像酒醒了一样,把你刚才点击的所有操作全部都按顺序执行了一遍。 4.11队列的抽象数据...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    4.9.3中缀表达式转后缀表达式 108 4.10队列的定义 111 电脑有时会处于疑似死机的状态。就当你失去耐心,打算了reset时。突然它像酒醒了一样,把你刚才点击的所有操作全部都按顺序执行了一遍。 4.11队列的抽象数据...
  • 4.8.1 斐波那契数列实现 101 4.8.2 递归定义 103 4.9 的应用--四则运算表达式值 104 4.9.1 后缀(逆波兰)表示法定义 104 4.9.2 后缀表达式计算结果 106 4.9.3 中缀表达式转后缀表达式 108 4.10 队列的定义 111...
  • 4.9.3中缀表达式转后缀表达式 108 4.10队列的定义 111 电脑有时会处于疑似死机的状态。就当你失去耐心,打算了reset时。突然它像酒醒了一样,把你刚才点击的所有操作全部都按顺序执行了一遍。 4.11队列的抽象数据...
  • 4.9.3中缀表达式转后缀表达式 108 4.10队列的定义 111 电脑有时会处于疑似死机的状态。就当你失去耐心,打算了reset时。突然它像酒醒了一样,把你刚才点击的所有操作全部都按顺序执行了一遍。 4.11队列的抽象数据...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    4.9.3 中缀表达式转后缀表达式 108 4.10 队列的定义 111 电脑有时会处于疑似死机的状态。就当你失去耐心,打算了Reset时。突然它像酒醒了一样,把你刚才点击的所有操作全部都按顺序执行了一遍。 4.11 队列的抽象...
  • Java开发技术大全(500个源代码).

    热门讨论 2012-12-02 19:55:48
    compare.java 演示前缀、后缀自加之间区别的程序 constCharExample.java 演示转义字符 converseNumber.java 逆向输出数字 daffodilNumber.java 水仙花数 division.java 演示整除结果 errorCompoundVariable....
  • 10.以下表达式的值,写出您想到的一种或几种实现方法: 1-2+3-4+……+m [Page] 答: int Num = this.TextBox1.Text.ToString() ; int Sum = 0 ; for (int i = 0 ; i ; i++) { if((i%2) == 1) { Sum += i ; ...

空空如也

空空如也

1 2
收藏数 23
精华内容 9
关键字:

如何利用栈求后缀表达式