精华内容
下载资源
问答
  • 一、目的理解中缀表达式求值的过程理解中缀转后缀表达式求值的过程掌握堆栈的应用二、问题描述缀表达式,其中包含括号,加减乘除,乘方等运算,利用中缀表达式,对表达式分析并求值入的中缀表达式转换为后缀形式,...

    一、目的

    • 理解中缀表达式求值的过程
    • 理解中缀转后缀表达式求值的过程
    • 掌握堆栈的应用

    二、问题描述

    • 缀表达式,其中包含括号,加减乘除,乘方等运算,利用中缀表达式,对表达式分析并求值
    • 入的中缀表达式转换为后缀形式,显示后缀形式,并通过后缀形式求值

    三、数据结构

    1. //运算符结构体
    2. typedef struct
    3. {
    4. char OPname; //存储运算符
    5. int inOP; //存储栈内级别
    6. int outOP; //存储栈外级别
    7. }OP;
    8. //定义运算数栈
    9. typedef struct
    10. {
    11. datatype data[MAXSIZE];
    12. int top;
    13. }SeqStack;
    14. //定义运算符栈
    15. typedef struct
    16. {
    17. char data[MAXSIZE];
    18. int top;
    19. }charStack;
    20. //----------------定义运算符数组-----------------//
    21. OP OPPree[OPNUM] =
    22. {
    23. {'+',3,2},
    24. {'-',3,2},
    25. {'*',5,4},
    26. {'/',5,4},
    27. {'^',7,6},
    28. {'(',1,8},
    29. {')',0,1},
    30. {'#',-1,-1}
    31. };

    四、算法设计的思想描述

    建立两个栈,一个为char类型栈OPTR,另一个为int类型栈OPND,分别来存储运算符和运算数。

    96136238a4ad7695024caa0011153d0d.png

    a86ac6e3395a771c79ff959e4d95290c.png

    参考文档和完整的文档和源码下载地址:

    https://www.write-bug.com/article/1409.html

    展开全文
  • 我们今天继续看一下,如何使用栈完成标准的四则混合运算表达式求值。不同于后缀表达式,遇到一个运算符就可以直接从栈里取两个数进行运算。在标准的四则混合运算表达式中(或者我们称之为中缀表达式),遇到一个操作符...

    我们今天继续看一下,如何使用栈完成标准的四则混合运算表达式求值。

    不同于后缀表达式,遇到一个运算符就可以直接从栈里取两个数进行运算。在标准的四则混合运算表达式中(或者我们称之为中缀表达式),遇到一个操作符是不能直接计算的,因为计算的顺序要取决于后面的运算符。多举几个例子,大家就能明白了。由于加和减是相同的运算优先级,乘和除是相同的运算优先级,我们就只用加和乘来举例就可以了。

    我们像计算后缀表达式一样,引入一个操作数栈。由于后缀表达式不用缓存 +-*/ 这些操作符,所以一个操作数栈就够了。但是,中缀表达式的计算是要用到操作符的缓存的,所以,我们还要再引入一个操作符栈,专门存储各个操作符。

    第一个例子:a + b * c,我们从前向后扫描,遇到a,压到操作数栈里,遇到 + ,压到操作符栈里,下一个是 b,此时,我们是不能像后缀表达式求值那样,直接计算 a + b,然后压栈的。因为我们不确定,b 是否会先参与后面的运算,所以我们只能把 b 先压栈,继续向后扫描。看到 * 以后,再把 * 压到操作符栈里;看到 c 以后,也要把 c 先压栈,理由与 b 压栈相同。接下来,再往下扫描,就发现已经到了末尾了。那我们就可以放心地从操作符栈里取出顶上的操作符,在这个例子中,就是 *,然后再从操作数栈里取出两个操作数,就是 b 和 c,然后把b和c的积,不妨记为d,放到操作数栈里。接下来,再去看操作符栈里,还有一个 +,那就把 + 取出来,然后去操作数栈里取出 a 和 d,计算它们的和,这就是最终的结果了。

    第二个例子:a + b + c,我们从前向后扫描,遇到a,压到操作数栈里,遇到 + ,压到操作符栈里,下一个是 b,压到操作数栈里。再下一个,又是 + ,由于加法的结合律,我们知道,先把a + b 的结果计算出来,或者后计算,都不会影响最终的结果。所以我们就把能做的化简先做掉。就是说,在扫描到第二个操作符是 + 以后,我们就把第一个操作符取出来,再把两个操作数取出来,求和并且把和送到操作数栈里。接下来的过程与第一个例子是相同的,不再赘述了。

    通过这两个例子,我们看到,一个操作符究竟什么时候进行运算,并不取决于它前面的那个操作符是什么,而是取决于它后面的那个操作符是什么。更具体一点讲:如果后面的操作符的运算优化级比前面的操作符高,那么前面的操作符就必须延迟计算;如果后面的操作符优化级比前面的低或者相等,那么前面的操作符就可以进行计算了。上面这句话,非常重要,是我们这节课的核心。请多读几遍,结合上面的两个例子,务必想明白它。

    好了,理解了这个,就可以上代码了。

    先看 Stack的完整定义:

    class Stack { private ArrayList list; public Stack(int size) { this.list = new ArrayList(size); } public T getTop() { if (isEmpty()) return null; return list.get(list.size() - 1); } public void push(T t) { this.list.add(t); } public T pop() { if (isEmpty()) return null; return list.remove(list.size() - 1); } public boolean isEmpty() { return list.isEmpty(); }}

    然后我们创建两个栈,一个是操作数栈,一个是操作符栈:

    public class StackExpression { public static void main(String args[]) throws IOException { TokenStream ts = new ExpressionTokenStream(System.in); Stack numbers = new Stack<>(100); Stack operators = new Stack<>(100); }}

    其中,TokenStream 是这节课里的课后作业:适配器模式

    按照上面分析的算法,如果遇到数字,就压栈到numbers里,如果遇到操作符,就要看前面一个的操作符的优先级是否比当前操作符高,如果前一个操作符高,那么执行前一个操作符的操作,如果是后面的高,那就只要把后面的操作符压栈即可:

    public class StackExpression { public static void main(String args[]) throws IOException { TokenStream ts = new ExpressionTokenStream(System.in); Stack numbers = new Stack<>(100); Stack operators = new Stack<>(100); while (ts.getToken().tokenType != Token.TokenType.NONE) { if (ts.getToken().tokenType == Token.TokenType.INT) { numbers.push((Integer)ts.getToken().value); ts.consumeToken(); } else { if (operators.getTop() == null || preOrder( operators.getTop().tokenType, ts.getToken().tokenType) < 0) { operators.push(ts.getToken()); ts.consumeToken(); } else { binaryCalc(numbers, operators); operators.push(ts.getToken()); ts.consumeToken(); } } } while (!operators.isEmpty()) { binaryCalc(numbers, operators); } System.out.println("result is " + numbers.getTop()); } private static void binaryCalc(Stack numbers, Stack operators) { int a = numbers.pop(); int b = numbers.pop(); Token oprt = operators.pop(); int d = 0; if (oprt.tokenType == Token.TokenType.PLUS) d = b + a; else if (oprt.tokenType == Token.TokenType.MULT) d = a * b; else if (oprt.tokenType == Token.TokenType.MINUS) d = b - a; else if (oprt.tokenType == Token.TokenType.DIV) d = b / a; numbers.push(d); } private static int preOrder(Token.TokenType left, Token.TokenType right) { if (left == Token.TokenType.PLUS || left == Token.TokenType.MINUS) { if (right == Token.TokenType.MULT || right == Token.TokenType.DIV) return -1; else return 1; } else return 1; }}

    好了。我们的这个程序已经可以处理类似 a + b - c * d + e / f 这样的算式了。

    为了让大家看得更清楚,我用图把 a + b * c / d 的过程画一遍。

    首先,遇到 a ,把 a 送到操作数栈,遇到 + ,送到操作符栈:

    f3456a1ce57bb41a56fa92d9c1d17b9f.png

    遇到 b,压栈

    247aa55a9b02049347b48939d96baff8.png

    遇到乘,由于乘的优先级高于加,所以,现在就什么也不做,只把乘号进栈:

    b05c3ce8d1c746008e542d6f714d0fb6.png

    同样,遇到 c 把 c 进栈(此图略,请自己补上),再遇到 / ,由于除的优先级与 * 的优先级相同,所以,乘就可以先做了。这个动作是把乘号出栈,把c 和 b出栈,求 c * b的值,并且把这个值入栈。即:

    f10865497986d2d87356dee66c7d6abd.png

    然后把 / 入栈,把 d 入栈:

    5874f8758e23edf487b109a1e15252b8.png

    现在到了运算的结尾了。我们只需要把现在的栈里的内容从顶向下计算起来即可,先算除法:

    ed5c3d1fda5dda10e92b610d943c35a4.png

    再算加法:

    f1e15ae1029f4e55178af65218bfa012.png

    但是,括号怎么办?

    可以这样想,在遇到形如 a * (b + c) 这样的形式的时候,左边的乘法是一定不能做的,我们只需要将左括号进栈即可。所以,我们可以把TokenStream里取得的左括号看做是一个优先级无穷大的运算符,它使得左方的运算符都不能提前进行计算。

    遇到右括号时,b + c 这个加法是可以进行运算的了,所以可以把右括号看作是一个优先级无穷小的运算符,它会使得操作符栈上的所有运算符都出栈并执行计算,直到遇到左括号。遇到左括号以后,只需要把左括号从栈里弹出来,然后让它和右括号一起狗带即可(这就是括号匹配啊,同学们~)。由于括号内的计算都已经完成了,结果是一个整数,我们已经在计算的过程中把这个整数放到操作数栈里了。所以整个括号内的求值就完成了。

    好了。今天的课程很短,但是比较难理解,尤其是,今天的程序都依赖于本周前边的课程。请务必先完成本周前边的课程再来看这节课。

    演示一下,我的完整版的效果:

    d38db892325e49395fd29f3dd97b7305.png
    展开全文
  • C语言中缀表达式求值(综合)

    千次阅读 多人点赞 2019-04-13 10:59:06
    基本思路:先把输入的中缀表达式→后缀表达式→进行计算得出结果 栈:”先进先出,先进后出“! 中缀转后缀(先把转换后的后缀表达式存入字符数组):从左至右依次读取,遇到运算数存入字符数组,遇到运算符压入栈...

    题前需要了解的:中缀、后缀表达式是什么?(不知道你们知不知道,反正我当时不知道,搜的百度)

    在这里插入图片描述

    基本思路:先把输入的中缀表达式→后缀表达式→进行计算得出结果
    栈:”先进先出,先进后出“!

    1. 中缀转后缀(先把转换后的后缀表达式存入字符数组):从左至右依次读取,遇到运算数存入字符数组,遇到运算符压入栈,继续读取–如果遇到的运算符优先级比栈顶的运算符优先级或者相等(比如“+与+或-” ----- “* 与 或/”------“/与/或”),则先将栈中的运算符输送至字符数组(如果栈中有“(”,则只输出到左括号就停止输出,不输出左括号),继续读取–如果遇到运算符优先级比栈顶运算符高的则入栈成为新的栈顶运算符,继续读取----如果遇到“)”,则将栈元素输出至字符数组,直至输出至”(“停止(在后缀表达式中没有括号,所以括号不输出入字符数组),直至读取完毕,然后将栈中剩余的运算符输出至字符数组。完毕!(注意:在遇到右括号”)“后就要将”(“左括号从栈中删除了,因为为防止将括号输出至字符数组)。

    2. 后缀表达式求值:从左至右读取,遇到运算数则将其存入栈中,遇到运算符(比如”/“)则将栈顶元素的前一个运算数(比如temp1)与栈顶元素(比如temp2)出栈(–注意–)并进行运算,temp1/temp2,并将其最终结果重新压入栈中成为新的栈顶元素,直至得出最终结果。


    上代码:

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define MAX 100  
    typedef float Num;//为防止以后变换操作数类型需要 
    typedef struct
    {
    	Num data[MAX];
    	int top;
    }StackNum;//运算数栈 
    typedef struct
    {
    	char data[MAX];
    	int top;
    }StackChar;//运算符栈 
    //------函数声明---------
    void InitNum(StackNum *p);//运算数栈初始化 
    void PushNum(StackNum *p, Num e);//运算数压栈 
    void PopNum(StackNum *p, Num *e);//运算数出栈
    Num GetNum(StackNum p);//取栈顶元素 
    //-----------------------
    void InitChar(StackChar *p);//运算符栈初始化
    void PushChar(StackChar *p, char e);//运算符压栈 
    void PopChar(StackChar *p, char *e);//运算符出栈 
    //-----------------------
    void Fun(StackNum *p, char e);//计算并压入运算数栈 
    //-----------------------
    void main()
    {
    	int i;//循环变量 
    	Num temp;//存放一个临时转换数
    	char str[MAX], ch;//存放中缀表达式原式,临时运算符 
    	//-----------
    	StackNum n1;
    	StackChar c1;
    	InitNum(&n1);
    	InitChar(&c1);
    	//------------
    	
    	for (;;)
    	{
    		printf("请输入中缀表达式:");
    		gets(str);
    		/*
    		注意字符串输入函数与scanf("%s",str) 的区别,scanf遇到空白字符,
    		包括空格,制表符,换行符时均会停止输入,所以不可取,而gets功能为读入一行,
    		并将换行符转换为字符串结束符。
    		*/
    		for (i = 0; str[i] != '\0'; i++)//读完整字符串-----字符串结束标志'\0' 
    		{
    			if (str[i] >= '0'&&str[i] <= '9')//分岔点一:----------------------------------------------------------------如果为数字 
    			{
    				temp = str[i] - '0';//-----将字符转换为数值 
    
    
    				while (str[i + 1] != '\0')//多位数值获取 
    				{
    					if (str[i + 1] >= '0'&&str[i + 1] <= '9')
    					{
    						temp = temp * 10 + str[i + 1] - '0';//------注意! 
    
    						i++;
    					}
    					else
    						break;//如果不是多位数字,则跳出多位获取循环 
    				}
    				PushNum(&n1, temp);//将获取来的数值入栈 
    			}
    			else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')')//分岔点二:-------如果为运算符 
    			{
    				switch (str[i])//表达式可为:整型/字符型/枚举型-----C语言中 
    				{
    					//case 后可为 整型,字符型----C语言中 
    				case '+':
    					if (c1.data[c1.top - 1] != '+'&&c1.data[c1.top - 1] != '-'&&c1.data[c1.top - 1] != '*'&&c1.data[c1.top - 1] != '/')
    					{
    						PushChar(&c1, '+');
    					}
    					else//如果不然,则将之前的先都出栈并计算,然后再入栈
    					{
    						while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算,其中括号内的优先级最高 
    						{
    							PopChar(&c1, &ch);
    							Fun(&n1, ch);//计算,并压运算数栈
    
    						}
    						PushChar(&c1,'+');
    					}
    					; break;
    				case '-':
    					if (c1.data[c1.top - 1] != '+'&&c1.data[c1.top - 1] != '-'&&c1.data[c1.top - 1] != '*'&&c1.data[c1.top - 1] != '/')
    					{
    						PushChar(&c1, '-');
    					}
    					else//如果不然,则将之前的先都出栈并计算,然后再入栈
    					{
    						while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算,其中括号内的优先级最高 
    						{
    							PopChar(&c1, &ch);
    							Fun(&n1, ch);//计算,并压运算数栈
    
    						}
    						PushChar(&c1, '-');
    					}
    					; break;
    				case '*':
    					if (c1.data[c1.top - 1] != '*'&&c1.data[c1.top - 1] != '/')
    					{
    						PushChar(&c1, '*');
    					}
    					else//如果不然,则将之前的先都出栈并计算,然后再入栈
    					{
    						while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算,其中括号内的优先级最高 
    						{
    							PopChar(&c1, &ch);
    							Fun(&n1, ch);//计算,并压运算数栈
    
    						}
    						PushChar(&c1, '*');
    					}
    					; break;
    				case '/':
    					if (c1.data[c1.top - 1] != '*'&&c1.data[c1.top - 1] != '/')
    					{
    						PushChar(&c1, '/');
    					}
    					else//如果不然,则将之前的先都出栈并计算,然后再入栈
    					{
    						while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算,其中括号内的优先级最高 
    						{
    							PopChar(&c1, &ch);
    							Fun(&n1, ch);//计算,并压运算数栈
    
    						}
    						PushChar(&c1, '/');
    					}
    					; break;
    				case '(':
    
    					PushChar(&c1, '(');
    
    					; break;
    				case ')'://并没有将'('压入栈中,只是当作一种出栈信号 
    					while (c1.data[c1.top - 1] != '(')
    					{
    						PopChar(&c1, &ch);
    						Fun(&n1, ch);//计算,并压运算数栈
    					}
    					PopChar(&c1, &ch);//将'('也出栈,但并不计算 
    					; break;
    				}
    
    			}
    		}
    		while (c1.top > 0)//将剩余的运算符出栈并计算 
    		{
    			PopChar(&c1, &ch);
    			Fun(&n1, ch);
    		}
    		printf("\t\t%s=%.2f", str, GetNum(n1));
    		printf("\n");
    		system("pause");
    	}
    	
    }
    void InitNum(StackNum *p)
    {
    	p->top = 0;
    }
    void InitChar(StackChar *p)
    {
    	p->top = 0;
    }
    void PushNum(StackNum *p, Num e)
    {
    	if (p->top == MAX)
    		printf("运算数栈满!\n");
    	else
    	{
    		p->data[p->top] = e;
    		p->top++;
    	}
    }
    void PushChar(StackChar *p, char e)
    {
    	if (p->top == MAX)
    		printf("运算符栈满!\n");
    	else
    	{
    		p->data[p->top] = e;
    		p->top++;
    	}
    }
    void PopNum(StackNum *p, Num *e)
    {
    	if (p->top == 0)
    		printf("运算数栈空!\n");
    	else
    	{
    		p->top--;
    		*e = p->data[p->top];
    	}
    }
    void PopChar(StackChar *p, char *e)
    {
    	if (p->top == 0)
    		printf("运算符栈空!\n");
    	else
    	{
    		p->top--;
    		*e = p->data[p->top];
    	}
    }
    void Fun(StackNum *p, char e)
    {
    	Num temp1, temp2;//存放两个临时操作数 
    	PopNum(p, &temp2);
    	PopNum(p, &temp1);
    	switch (e)
    	{
    	case '+':PushNum(p, temp1 + temp2); break;
    	case '-':PushNum(p, temp1 - temp2); break;
    	case '*':PushNum(p, temp1*temp2); break;
    	case '/':PushNum(p, temp1 / temp2); break;
    
    	}
    }
    Num GetNum(StackNum p)
    {
    	return p.data[p.top - 1];
    }
    

    因为我也是个小菜鸟,所以本次也全当作笔记总结的文章,我又找了两篇我参考的大佬的文章,如下:

    原文:https://blog.csdn.net/myCsdn_Xm/article/details/80861183

    后缀表达式的求值(c语言)

    题目描述
    为了便于处理表达式,常常将普通表达式(称为中缀表示)转换为后缀{运算符在后,如X/Y写为XY/表达式。在这样的表示中可以不用括号即可确定求值的顺序,如:(P+Q)(R-S) → PQ+RS-。后缀表达式的处理过程如下:扫描后缀表达式,凡遇操作数则将之压进堆栈,遇运算符则从堆栈中弹出两个操作数进行该运算,将运算结果压栈,然后继续扫描,直到后缀表达式被扫描完毕为止,此时栈底元素即为该后缀表达式的值。
    输入
    输入一行表示后缀表达式,数与数之间一定有空格隔开(可能不只一个空格),最后输入@表示输入结束。

    数据保证每一步的计算结果均为不超过100000的整数。

    输出
    输出一个整数,表示该表达式的值.
    样例输入
    14 3 20 5 / *8 - + @
    样例输出
    18

    #include<stdio.h>
    
    typedef struct STRACK                                              //定义结构体
    {
        double a[100];
        int top;
    } STRACK;
    
    int main()
    {
        double totle=0,e=0;
        char s[100];
        int i;
    
        STRACK L;
        L.top=-1;
        gets(s);
        for(i=0; s[i]!='@'; i++)
        {
            if(s[i]<='9'&&s[i]>='0')
            {
                L.top++;
                int temp=s[i]-'0';
                int k=i+1;
                while(s[k]!='@')                                          //利用while循环得到由多位由字符组成的数值
                {
                    if(s[k]<='9'&&s[k]>='0')
                    {
                        temp=10*temp+(s[k]-'0');
                        i++;
                        k++;
                    }
                    else break;
                }
                L.a[L.top]=temp;
            }
            else  if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')        //遇到运算符进行计算
            {
                switch(s[i])
                {
                case '+':
                    e=L.a[L.top-1]+L.a[L.top];
                    break;
                case '-':
                    e=L.a[L.top-1]-L.a[L.top];
                    break;
                case '*':
                    e=L.a[L.top-1]*L.a[L.top];
                    break;
                case '/':
                    e=L.a[L.top-1]/L.a[L.top];
                    break;
                }
                L.a[L.top-1]=e;                                          //往前一位存储
                L.a[L.top]=0;
                L.top--;
            }
        }
        printf("%.0lf",L.a[L.top]);                                    //输出最后结果
        return 0;
    }
    

    原文:https://blog.csdn.net/hanmiaobei7428/article/details/82049881

    中缀表达式的求值问题

    表达式的求值问题(堆栈)
    0. 解决目标
    将形如2*(9+6/3-5)+4表达式求值的思想

    1. 后缀表达式的求值

    形如在这里插入图片描述这里写图片描述的表达式如何求值?

    (翻译成中缀表达式为:6/2-3+4*2,我们不进行中缀表达式的翻译操作,只是为了方便理解中间的过程)
    从左向右“扫描”,逐个处理运算数和运算符号

    遇到运算数怎么办?如何“记住”目前还不未参与运算的数?

    遇到运算符号怎么办?对应的运算数是什么?
    在这里插入图片描述
    下图是一种解决办法。
    在这里插入图片描述
    这里使用一种结构,由于长得像先称之为“槽”,这种槽有什么特点?

    1.只能存放数字
    2.存放的数字只能后面进来的先出
    这里有个问题,如果是符号怎么办呢?
    我们提供一种解决办法,如果遇到符号,则将槽最顶部的数字与前一个数字从槽中拿出,进行操作,操作为:

    1.前一个数字 运算符 槽最顶部的数字
    2.并讲运算结果 再放入槽中
    3.直至所有东西都按从左到右的顺序 尝试进入槽中,便得到结果。

    这种能够解决后缀表达式的求值问题的结构——“槽”,就是堆栈。它是一种线性存储结构,后入先出。
    我们用堆栈解决了后缀表达式的求值问题,那么问题来了,如何将中缀表达式转换成后缀表达式呢?
    ##2. 中缀化后缀

    目标:将形如2*(6/3+4)-5的中缀表达式化成 2 6 3 / 4 + * 5 -的后缀表达式
    带括号的表达式看起来比较复杂,我们先看没有括号的转换。

    小目标:将形如2+9/3-5的中缀表达式化成2 9 3 / + 5 - 的后缀表达式
    构造一种堆栈,只能存放符号,同样遵循后入先出的原则。
    有两个问题
    1.遇到数字怎么办?
    2.堆栈中的符号怎么处理?
    第一个问题很简单,输出即可,因为我们只需要求表达式,并不需要同时计算。
    第二个问题,因为符号有优先级,当将符号放入堆栈时,比较其与前一个符号的优先级,若低于,则先输出前一个运算符。这个也很好理解,高优先级的运算先进行。
    解决过程如下图所示。
    在这里插入图片描述
    那如果带括号要怎么解决呢?问题有:

    1.括号也算一种符号,但括号不参与运算,
    2.括号提供一种优先级,括号里面的运算优先级最高

    第一个问题,我们在后缀表达式转换成值的时候是直接进行操作的,利用顺序已经将括号的功能包括进去,但只是不显示括号而已。具体解决是在一对括号齐全时,将其中的运算符输出。
    第二个问题,我么将括号放入堆栈之前认为其优先级最高,在放入堆栈之后,将其认为优先级最低,即只进行括号里面的优先级比较(忽略括号)。
    解决过程如下图。

    在这里插入图片描述
    总结中缀表达式转化成后缀表达式的方法如下:

    在这里插入图片描述
    按照 步骤2->1->0 完成目标


    学习自《数据结构:陈越》之线性结构


    呼,终于把最近看的,学的,总结起来了。。。
    我如果有什么地方弄得不对的,看到的道友可以在下方评论说出来,或者私信我。
    学习使我们快乐~

    展开全文
  • (一)逆波兰表达式介绍:表达式一般由操作数(Operand)、运算符(Operator)组成,例如算术表达式中,通常把运算符放在两个操作数的中间,这称为中缀表达式(Infix Expression),如A+B。波兰数学家Jan Lukasiewicz提出...

    (一)逆波兰表达式介绍:

    表达式一般由操作数(Operand)、运算符(Operator)组成,例如算术表达式中,通常把运算符放在两个操作数的中间,这称为中缀表达式(Infix Expression),如A+B。

    波兰数学家Jan Lukasiewicz提出了另一种数学表示法,它有两种表示形式:

    把运算符写在操作数之前,称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression),如+AB;把运算符写在操作数之后,称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression),如AB+;前后缀表达式的出现是为了方便计算机处理,它的运算符是按照一定的顺序出现,所以求值过程中并不需要使用括号来指定运算顺序,也不需要考虑运算符号(比如加减乘除)的优先级。

    先介绍中简单的人工转化方法:

    假设有一个中缀表达式a+b*c-(d+e):

    1. 首先将这个中缀表达式的所有运算加括号((a+(b*c))-(d+e))
    2. 然后将所有运算符放到括号后面,这样就变成了((a(bc)* )+ (de)+ )-
    3. 把所有括号去掉abc*+de+-,最后得出的结果就是后缀表达式。

    (二)算法

    一、 将中缀表达式转换成后缀表达式算法:

    从左到右遍历中缀表达式的每一个数字和符号,若是数字就输出即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级(没有括号,乘除优先于加减),是右括号或优先级低于栈顶符号,则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最后输出后缀表达式为止。

    单把优先级低于栈顶符号,则栈顶元素依次出栈并输出这句话截取出来如何思考?这样做的结果优先级高的将更靠近操作数,在后缀表达式进行求值的时候,就会被先计算;其实后缀表达式已经把优先级蕴含在顺序中了。

    二、逆波兰表达式求值算法:

    1、循环扫描语法单元的项目。

    2、如果扫描的项目是操作数,则将其压入操作数堆栈,并扫描下一个项目。

    3、如果扫描的项目是一个二元运算符,则对栈的顶上两个操作数执行该运算。

    4、如果扫描的项目是一个一元运算符,则对栈的最顶上操作数执行该运算。

    5、将运算结果重新压入堆栈。

    6、重复步骤2-5,堆栈中即为结果值。

    二、将中缀表达式转换成前缀表达式算法:

    从右到左遍历中缀表达式的每一个数字和符号,若是数字就输出即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级(没有括号,乘除优先于加减),是左括号或优先级高于栈顶符号,则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最后输出前缀表达式为止。

    二、波兰表达式求值算法:

      1、从右到左依次扫描语法单元的项目。

      2、如果扫描的项目是操作数,则将其压入操作数堆栈,并扫描下一个项目。

      3、如果扫描的项目是一个二元运算符,则对栈的顶上两个操作数执行该运算。

      4、如果扫描的项目是一个一元运算符,则对栈的最顶上操作数执行该运算。

      5、将运算结果重新压入堆栈。

      6、重复步骤2-5,堆栈中即为结果值。

    8774f3d5a3d0ba00f983dce9dc07a398.png

    (三)代码实现:

    package 
    展开全文
  • 欢迎关注微信公众号:计算机二级...在逻辑表达式求值过程中,按其操作数从左至右的计算顺序,当某个操作数的值可以确定整个逻辑表达式的值时,其余的操作数不再计算。逻辑运算符“&&”和“||”都具有短...
  • 算法,表达式求值后缀表达式求值介绍后缀表达式求值和上一节的“中缀表达式转换为后缀表达式”有所不同,在对后缀表达式进行从左至右的扫描过程当中,由于操作符在操作数的后面,所以要找一个容器把操作数暂时存放...
  • 如: 3+5,6+8称为逗号表达式,又称为“顺序求值运算符”。逗号表达式的一般形式为 表达式1,表达式2逗号表达式的求解过程是:先求解表达式1,再求解表达式2。整个逗号表达式的值是表达式2的值。例如,上面的逗号...
  • 从书上看到的讲起最近(半年内 )在看《大话数据结构》,上个星期在栈这一节看到了后缀表达式用于...后缀表达式求值规则(《大话数据结构》)中缀转后缀规则(《大话数据结构》)当尝试了之后发现,上面的描述没有...
  • 一、使用说明1.1 项目简介表达式求值是程序设计语言编译中的一个最基本的问题,就是将一个表达式转化为逆波兰表达式并求值。具体要求是以字符序列的形式从终端输入语法正确的、不含变量的整数表达式,并利用给定的...
  • C的基本程序步骤由语句 (statements) 组成,而大多数语句都由表达式 expression) 构成。因此,我们先学习表达式。 1 表达式表达式(expression)由运算符和运算对象组成。最简单的表达式是一个单独的运算对象,以此为...
  • 前言 最近开始刷题,真实地解决了大学时期“这黑窗口敲来敲去做数学题有卵用?...前缀、中缀以及后缀表达式是什么? 先聚合一下定义,以后万一要复习也好找XD前缀表达式 波兰表示法(Polish notation...
  • 表达式表达式是由运算符和操作数组合构造成。...每一个表达式都有一个值,求值的过程依赖于运算符优先顺序。加减乘除这四种运算遵循算术运算的优先级法则。当表达式中混合有不同类型的操作数时,会执行自动类型...
  • 接下来就为大家讲解一下这份由iMindMap制作的C语言表达式思维导图。C语言表达式一共有五块内容。一、算术运算符顾名思义,算术运算符就是我们在进行算式计算时使用到的运算符。图片1:算术运算符在C语言中,根据参与...
  • 1.数制转换数值进位制的换算是计算机实现计算和处理的基本问题。比如将十进制数m转换为...其基本原理是:m=(m / n)* n + m % n ( 其中: / 为整除,%为余 )例 将十进制数1567转换为八进制数。设m=1567 ,n=8。按照...
  • 150. 逆波兰表达式求值根据 逆波兰表示法,求表达式的值。有效的运算符包括 + , - , * , / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。说明:整数除法只保留整数部分。给定逆波...
  • C语言提供了一组逻辑运算符:或(||)、且(&&)、非(!),分别对应于命题逻辑中的 OR、AND、NOT运算。逻辑运算符:或 ||。在命题逻辑中,当P=1或Q=1时,P||Q等于1。逻辑运算符:且 &&。在命题逻辑中,当...
  • 什么是表达式?计算机如何表达和计算一个算术表达式?搞懂了这个问题,我们也就弄清楚了如何去解析一...表示一个算术表达式的方法通常有三种,前缀表达式,也称为波兰表达式、中缀表达式,也就是我们人类常用的这种...
  • 表达式求值问题例题1.中缀表达式转前缀表达式2.中缀表达式转后缀表达式实现过程:3. 递归:递归产生的问题:1.括号匹配问题栈例题1算法思想:1)初始一个空栈,顺序读入括号。若是右括号,则与栈顶元素进行匹配·若...
  • 题目如下程序,如何实现数据测试以及输出:学前...如:我们平时写a+b,这是中缀表达式,写成后缀表达式就是:ab+(a+b)*c-(a+b)/e的后缀表达式为:(a+b)*c-(a+b)/e→((a+b)*c)((a+b)/e)-→((a+b)c*)((a+b)e/)-→(ab+...
  • 表达式可以嵌套,每个表达式都有一个。在计算时要考虑运算符的优先级、结合性及数据类型的转换;计算机中的表达式都写在一行中。表达式有算术、赋值、关系、逻辑、条件和逗号等。在表达式的后边加个分号就是表达式...
  • 数据结构源码笔记(C语言):英文单词按字典序排序的基数排序数据结构源码笔记(C语言):直接插入排序数据结构源码笔记(C语言):直接选择排序数据结构源码笔记(C语言):置换-选择算法数据结构源码笔记(C语言)...
  • 前言最近开始刷题,真实地解决了大学时期“这黑窗口敲来敲去做数学题有卵用?...前缀、中缀以及后缀表达式是什么?先聚合一下定义,以后万一要复习也好找XD前缀表达式波兰表示法(Polish notation,或波兰记法),...
  • Warning在观看本博客之前,请保证自己理解了表达式的三种表达方式。本文旨在让大家更深层次的了解表达式,基础的知识就是上方的链接中所写的。所以,在了解后缀表达式的运算原理之后,我将不会讲述类似的前缀表达式...
  • 唯一知道的是,几乎所有C语言教材都这么讲:i++就是先使用i的再使i自身加一,而++i则是先使i自身加一,然后在使用i的。出于对真理的追求。今天我们彻底弄明白此问题。譬如这样的话:int a,b;int i=10,j=10;a=i+...
  • 第三章:栈和队列下面讲解栈的应用主要内容有:栈的应用、括号匹配、中 后 前 缀表达式转换1.栈的应用1.1括号匹配我们在数学运算中 [(A+b)*c] - (E-F) 往往都会有[ ] 和 ( ) 来表示运算的优先级,我们把这样的[ ] 和...
  • 一、后缀表达式求值 后缀表达式也叫逆波兰表达式,其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为:6523+ 8 * + 3+*,则其求值过程如下: 1)遍历表达式,遇到的数字首先放入栈中,此时栈如下所示: ...
  • #include #include int precedence(char c) {  if(c=='*'||c=='/')  return 2;  if(c=='+'||c=='-')  return 1;  return 0; } int main() {  cha

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 134
精华内容 53
关键字:

c语言中缀表达式求值

c语言 订阅