逆波兰式 订阅
逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后) 展开全文
逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)
信息
又    称
后缀表达式
使用方式
将运算符写在操作数之后
中文名
逆波兰式
外文名
Reverse Polish notation,RPN
逆波兰式定义
一个表达式E的后缀形式可以如下定义:(1)如果E是一个变量或常量,则E的后缀式是E本身。(2)如果E是E1 op E2形式的表达式,这里op是任何二元操作符,则E的后缀式为E1'E2' op,这里E1'和E2'分别为E1和E2的后缀式。(3)如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式。如:我们平时写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*)(ab+e/)-→ab+c*ab+e/-
收起全文
精华内容
下载资源
问答
  • 逆波兰式

    千次阅读 2018-03-30 17:34:22
    逆波兰式 Description 假设表达式由单字母变量和双目四则运算符构成,试编写程序,将一个通常书写形式且书写正确的表达式转换为逆波兰式。 Input 输入由单字母变量和双目四则运算算符构成的表达式。 Output ...
     

     

    逆波兰式

    Description

    假设表达式由单字母变量和双目四则运算符构成,试编写程序,将一个通常书写形式且书写正确的表达式转换为逆波兰式。

    Input

    输入由单字母变量和双目四则运算算符构成的表达式。

    Output

    输出其逆波兰式。

    Sample Input       (a+b)*c

    Sample Output    ab+c*

     

    更多测试用例如下:

    输入a*b+(c-d/e)*f                      输出ab*cde/-f*+

    输入a+b*(c-d)-e/f                      输出 abcd-*+ef/-

    输入a*(b*(c+d/e)-f)                    输出abcde/+*f-*

    /*逆波兰表示法,是一种逻辑、算术和代数表示方法,
    其特点是操作符置于操作数的前面,因此也称为前缀表示法。
    例如:“a+b”的波兰表示法为:“+ab”。
    逆波兰表示法是一种数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也称为后缀表示法。
    例如:“a+b”的逆波兰表示法为:“ab+”。
    题目要求将输入的波兰表示法表达式转换为逆波兰表示法表达式。 */
    /*基本思想:首先需要分配2个栈,一个作为临时存储运算符的栈S1 OPTR(含一个结束符号),
    一个作为输入逆 波兰式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,
    注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定非#不可。
    从中缀式的左端开始取字符,逐序进行如下步骤:
    (1)若取出的字符是 操作数,则分析出完整的运算数,该操作数直接送入S2栈
    (2)若取出的字符是 运算符,则将该运算符与S1栈栈顶元素比较,如果该 运算符优先级大于S1栈栈顶 运算符优先级,则将该运算符进S1栈,
    否则,将S1栈的栈顶运算符弹出,送入S2栈中,直至S1栈栈顶运算符低于(不包括等于)该运算符优先级,则将该运算符送入S1栈。
    (3)若取出的字符是“(”,则直接送入S1栈底。
    (4)若取出的字符是“)”,则将距离S1栈栈底最近的“(”之间的运算符,逐个 出栈,依次送入S2栈,此时抛弃“(”。
    (5)重复上面的1~4步,直至处理完所有的输入字符
    (6)若取出的字符是“#”,则将S1栈内所有运算符(不包括“#”),逐个 出栈,依次送入S2栈。
    完成以上步骤,S2栈便为逆 波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆 波兰式的计算方法计算了!*/
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define Stack_Size 100
    typedef struct
    {
        char elem[Stack_Size];
        int top;
    }SeqStack;
    void chushi(SeqStack *S)
    {
        S->top=-1;
    }
    int push(SeqStack *S,char x)
    {
        if(S->top==Stack_Size-1)return 0;
        S->top++;
        S->elem[S->top]=x;
        return 1;
    }
    int pop(SeqStack *S,char *x)
    {
        if(S->top==-1)
            return 0;
        else
            {
        *x=S->elem[S->top];
        S->top--;
        return 1;
            }
    }
    char GetTop(SeqStack *S)
    {
        if(S->top==-1)
        return 0;
            else
            {
                return  (S->elem[S->top]);
            }
    }
    int isempty(SeqStack *S)
    {
        if(S->top==-1)return 1;
        else return 0;
    }
    void nibolan(char *ch)
    {   SeqStack s1;SeqStack s2;
        chushi(&s1);
        chushi(&s2);
        push(&s1,'#');
        char x,p;int i;int j=0;int c[100];
        for(i=0;(ch[i]!='\0');i++)
        {   switch(ch[i])
         {
            case'(':push(&s1,ch[i]);break;
            case')':
                while(GetTop(&s1)!='(')
                {
                    pop(&s1,&x);
                    push(&s2,x);
                }
                pop(&s1,&x);break;
            case'+':
            case'-':
            while ((GetTop(&s1) != '#')&&(GetTop(&s1) != '('))
                {
                    pop(&s1,&x);
                    push(&s2,x);
                }
                push(&s1,ch[i]);
                break;
            case'*':
            case'/':
           while (GetTop(&s1) == '*' || GetTop(&s1) == '/')
                {
                    pop(&s1,&x);
                    push(&s2,x);
                }
                push(&s1,ch[i]);
                break;
           default:
                push(&s2,ch[i]);
         }
      }
      while((!isempty(&s1))&&(GetTop(&s1)!='#'))
      { //若栈s1不为空,将其中的元素依次弹出到s2
          pop(&s1,&x);
          push(&s2,x);
      }
    
    
    
    while(!isempty(&s2))
        { //栈未空,将栈低元素依次弹出
            pop(&s2,&p);
            c[j++] = p;
        }
        c[j]='\0';
         for(i=j-1;i>=0;i--)
         {
             printf("%c",c[i]);
         }
    }
    int main()
    {
        char ch[100];
        scanf("%s",ch);
        nibolan(ch);
        return 0;
    }

     

    展开全文
  • 波兰式、逆波兰式与表达式求值

    万次阅读 多人点赞 2018-12-30 11:22:11
    波兰式、逆波兰式与表达式求值  《数据结构》中关于栈的解释经常会涉及到逆波兰式,波兰式,中缀式表达式的求值问题。但是,十分惭愧,整个大一阶段, 数据结构的课程没有上够5节,没有意识要学习,吃亏真的很大...

    波兰式、逆波兰式与表达式求值

      《数据结构》中关于栈的解释经常会涉及到逆波兰式,波兰式,中缀式表达式的求值问题。但是,十分惭愧,整个大一阶段,

    数据结构的课程没有上够5节,没有意识要学习,吃亏真的很大,只能现在恶补了。废话不说了,进入正题。

     

    1. 中缀表达式

           人类最熟悉的一种表达式1+2,(1+2)*3,3+4*2+4等等都是中缀表示法。对于人们来说,也是最直观的一种求值方式,先算括号里的,
    然后算乘除,最后算加减,但是,计算机处理中缀表达式却并不方便,因为没有一种简单的数据结构可以方便从一个表达式中间抽出
    一部分算完结果,再放进去,然后继续后面的计算(链表也许可以,但是,代价也是不菲)。
           在介绍前缀,后缀表达式之前,我想先通过我们最熟悉的中缀表达式画出一棵语法树来直观认识前后缀表达式。以A+B*(C-D)-E*F为例:

    则中缀表达式得名于它是由相应的语法树的中序遍历的结果得到的。

     

     

    2. 前缀缀表达式

     

      前缀表达式又叫做波兰式。同样的道理,表达式的前缀表达式是由相应的语法树的前序遍历的结果得到的。

    如上图的前缀表达式为- + A * B - C D * E F

    由前缀表达式求出结果有下面两种思路:

      1.从左至右扫描表达式,如果一个操作符后面跟着两个操作数时,则计算,然后将结果作为操作数替换(这个操作符和两个操作数),

    重复此步骤,直至所有操作符处理完毕。如-+A*B-CD*EF,扫描到-CD时,会计算C-D=C',表达式变成:-+A*BC'*EF

    继续扫描到*BC',计算B*C'=B',表达式变成:-+AB'*EF,继续+AB',依此类推。

      2.由1.知,要多遍扫描表达式,并且需要将3个字符替换成1个,比较繁锁,我们可以用一个栈S2来实现计算,扫描从右往左进行,

    如果扫描到操作数,则压进S2,如果扫描到操作符,则从S2弹出两个操作数进行相应的操作,并将结果压进S2(S2的个数出2个进1个),

    当扫描结束后,S2的栈顶就是表达式结果。

     

    3. 后缀表达式

      后缀表达式又叫做逆波兰式。它是由相应的语法树的后序遍历的结果得到的。如上图的后缀表达式为:

    A B C D - * + E F * -

    由前缀表达式求出结果十分方便,只需要用一个栈实现:

    我们可以用一个栈S2来实现计算,扫描从左往右进行,如果扫描到操作数,则压进S2,如果扫描到操作符,则从S2弹出两个操作数

    进行相应的操作,并将结果压进S2(S2的个数出2个进1个),当扫描结束后,S2的栈顶就是表达式结果。后缀表达式和前缀表达式看

    起来就像一对逆过程,实际上并不是这样子,因为字符读取的时候都是从左往右的,所以,前缀表达式往往需要用两个栈来计算,

    其中一个栈用来预处理:将字符串倒序压进栈中。

     

    4. 中缀表达式转换成后缀表达式

      既然中缀表达式对于计算机的运算并不便利,而前缀后缀表达式的计算相对简单方便。因此,找到一种途径将中缀表达式

    转换成前缀后缀表达式就十分重要。实际上,二者的转换算法看起来也很像一个逆过程。因此,我们着重讨论中缀转后缀。

    从理论上讲,已知一棵二叉树的中序遍历序列,要求出它的后序遍历序列是不唯一的,即文法是有多义性的。但是,在这

    里加上了优先级这一限制条件,转换就变得唯一了。

     

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

    输入:中缀表达式串

    输出:后缀表达式串

    PROCESS BEGIN:

       1.从左往右扫描中缀表达式串s,对于每一个操作数或操作符,执行以下操作;

                    2.IF (扫描到的s[i]是操作数DATA)

             将s[i]添加到输出串中;

                   3.IF (扫描到的s[i]是开括号'(')

                            将s[i]压栈;

                   4.WHILE (扫描到的s[i]是操作符OP)

                           IF (栈为空 或 栈顶为'(' 或 扫描到的操作符优先级比栈顶操作符高)

                                 将s[i]压栈;

                                 BREAK;

                           ELSE

                                 出栈至输出串中

                   5.IF (扫描到的s[i]是闭括号')')

                           栈中运算符逐个出栈并输出,直到遇到开括号'(';

                           开括号'('出栈并丢弃;

                   6.返回第1.步

             7.WHILE (扫描结束而栈中还有操作符)

                            操作符出栈并加到输出串中

    PROCESS END

     

    4. 中缀表达式转换成前缀表达式

      中缀表达式转换成前缀表达式和中缀表达式转换成后缀表达式十分类似,只需要将扫描方向由前往后变成由后往前,

    将'('改为')',')'改为'(',注意其中一个判断优先级的地方需要由>=变成>.

      至此,理论基础已经讲完了,用一道OJ题目来客观认识一下会比较好理解。HDU2127

    Polish notation

    Time Limit: 10000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 112    Accepted Submission(s): 32

    Problem Description

    Now, give you a string of standard arithmetic expressions, please tell me the Polish notation and the value of expressions.

    Input

    There're have multi-case. Every case put in one line, the expressions just contain some positive integers(all less than 100, the number of integers less than 20), bi-operand operators(only have 3 kinds : +,-,*) and some brackets'(',')'.
    you can assume the expressions was valid.

    Output

    Each case output the Polish notation in first line, and the result of expressions was output in second line.
    all of the answers are no any spaces and blank line.the answer will be not exceed the 64-signed integer.

    Sample Input

    
     

    1+2-3*(4-5) 1+2*(3-4)-5*6

    Sample Output

    
     

    Case 1: - + 1 2 * 3 - 4 5 6 Case 2: - + 1 * 2 - 3 4 * 5 6 -31

    Author

    威士忌

    Source

    HDU 2007-10 Programming Contest

     

    解释:

      网上很少这道题的题解,我先写一个吧,前面题目扯了一堆废话(我全删掉了),只有一句最重要的:给你中缀表达式,求出它的波兰式并计算出

    结果。题目是很裸的将中缀表达式转换成前缀表达式,再进行计算出结果,可以直接套上面的算法。但是,这里有一些点易错点需要注意:

         1.转化后的前缀表达式需要留一个空格

      2.因为数字并不是1位的,因为数字<100,有可能有两位,所以,不能只读取一个字符做为数字,需要读取所有的数字,具体看代码对数字的处理

      3.要注意有可能超过int的范围,一开始就想当然地用int,结果WA,还要注意将字符串转化为__int64

    #include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    char stack[500];					//定义顺序栈,其中top==0表示栈为空;
    int top;							//栈顶指针,为0表示栈为空;
    char output[500], input[500];		//波兰式
    int outLen;
    
    int priority(char op)				//判断运算符级别函数;其中* /的级别为2,+ -的级别为1;
    {
    	if (op=='+' || op=='-')
    		return 1;
    	if (op=='*' || op=='/')
    		return 2;
    	else
    		return 0;
    }
    
    bool isOperator(char op)				//判断输入串中的字符是不是操作符,如果是返回true
    {
    	return (op=='+' || op=='-' || op=='*' || op=='/');
    }
    
    void Polish(char *s,int len)			//将一个中缀串转换为前缀串,
    {
    	memset(output,'\0',sizeof output);	//输出串
    	outLen = 0;
    	for (int i=len-1; i >= 0; --i)		//1)求输入串的逆序。
    	{
    		if (isdigit(s[i]))				//经验见:http://blog.csdn.net/linraise/article/details/18566319#comments
    		{
    			output[outLen++] = s[i];	//3)假如是操作数,把它添加到输出串中。
    			while (i-1 >= 0 && isdigit(s[i-1]))
    			{
    				output[outLen++] = s[i-1];
    				--i;
    			}
    			output[outLen++] = ' ';		//空格隔开
    		}
    		if (s[i]==')')				    //4)假如是闭括号,将它压栈。
    		{
    			++top;
    			stack[top] = s[i];
    		}
    		while (isOperator(s[i]))		//5)如果是运算符,执行算法对应操作;
    		{												//>=很重要
    			if (top==0 || stack[top]==')' || priority(s[i]) >= priority(stack[top])) //空栈||或者栈顶为)||新来的元素优先级更高
    			{
    				++top;
    				stack[top] = s[i];
    				break;
    			}
    			else
    			{
    				output[outLen++] = stack[top];
    				output[outLen++] = ' ';
    				--top;
    			}
    		}
    		if (s[i]=='(')					//6)假如是开括号,栈中运算符逐个出栈并输出,直到遇到闭括号。闭括号出栈并丢弃。
    		{
    			while (stack[top]!=')')
    			{
    				output[outLen++] = stack[top];
    				output[outLen++] = ' ';
    				--top;
    			}
    			--top;	// 此时stack[top]==')',跳过)
    		}
    		//7)假如输入还未完毕,跳转到步骤2。
    	}
    	while (top!=0)						//8)假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。
    	{
    		output[outLen++] = stack[top];
    		output[outLen++] = ' ';
    		--top;
    	}
    }
    
    char DstBuf[200];
    char* OP(char* op1,char* op2,char op)
    {
    	__int64 res = 0;
    	if (op=='+')
    		res = _atoi64(op1) + _atoi64(op2);
    	else if (op=='-')
    		res = _atoi64(op1) - _atoi64(op2);
    	else if (op=='*')
    		res = _atoi64(op1) * _atoi64(op2);
    	else if (op=='/')
    		res = _atoi64(op1) / _atoi64(op2);
    	_i64toa(res,DstBuf,10);
    	return DstBuf;
    }
    
    char cSt1[200][80], cSt2[200][80];
    __int64 calc(char *s)				//波兰式需要用两个栈,逆波兰式只需要一个栈
    {
    	int top1=0, top2=0, i;
    	for (i=0; s[i]; ++i)
    	{
    		if (s[i] && s[i] != ' ')
    		{
    			++top1;
    			sscanf(s+i,"%s",cSt1[top1]);		//初始化其中一个栈
    			while (s[i] && s[i] != ' ')
    				++i;
    		}
    	}
    	while (top1 != 0)	//栈不空
    	{
    		if (!isdigit(cSt1[top1][0]))	//是操作符
    		{
    			OP(cSt2[top2], cSt2[top2-1], cSt1[top1][0]);
    			memcpy(cSt2[top2-1],DstBuf,sizeof DstBuf);
    			--top2;						//操作数栈:出栈俩,进栈一
    			--top1;						//操作符出栈
    		}
    		else
    		{
    			++top2;						//数进操作数栈
    			memcpy(cSt2[top2],cSt1[top1],sizeof cSt1[top1]);
    			--top1;						//操作符出栈
    		}
    	}
    	return _atoi64(cSt2[1]);
    }
    int main()
    {
    #ifndef ONLINE_JUDGE
    	freopen("2.txt","r",stdin);
    #endif
    
    	int T = 1;
    	while (gets(input))
    	{
    		Polish(input, strlen(input));
    		reverse(output,output+outLen-1);
    		output[outLen-1] = '\0';
    		printf("Case %d:\n%s\n",T++,output);
    		printf("%I64d\n",calc(output));
    	}
    	return 0;
    }

    做完了波兰式,再看一个逆波兰式的题:HDU1237
    这道是裸的逆波兰,只是简化版本的,我用上面的算法往上一交,结果WA,测试了一下这个用例1 - 3 + 4,结果输出-6,显然是优先级顺序没有处理好,

    改了一下prirority就行了

    更简单的做法可以看这里,本质上是简化了的逆波兰式解法。

    #include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    char stack[500];					//定义顺序栈,其中top==0表示栈为空;
    int top;							//栈顶指针,为0表示栈为空;
    char output[500], input[500];		//波兰式
    int outLen;
    
    int priority(char op)				//判断运算符级别函数;其中* /的级别为2,+ -的级别为1;
    {
    	if (op=='+' || op=='-')
    		return 1;
    	if (op=='*' || op=='/')
    		return 2;
    	else
    		return 0;
    }
    
    bool isOperator(char op)				//判断输入串中的字符是不是操作符,如果是返回true
    {
    	return (op=='+' || op=='-' || op=='*' || op=='/');
    }
    
    void rePolish(char *s,int len)			//将一个中缀串转换为后缀串,
    {
    	memset(output,'\0',sizeof output);	//输出串
    	outLen = 0;
    	for (int i=0; i < len; ++i)			//1)求输入串的逆序。
    	{
    		if (isdigit(s[i]))				//经验见:http://blog.csdn.net/linraise/article/details/18566319#comments
    		{
    			output[outLen++] = s[i];		//3)假如是操作数,把它添加到输出串中。
    			while (i+1 < len && isdigit(s[i+1]))
    			{
    				output[outLen++] = s[i+1];
    				++i;
    			}
    			output[outLen++] = ' ';		//空格隔开
    		}
    		if (s[i]=='(')					//4)假如是闭括号,将它压栈。
    		{
    			++top;
    			stack[top] = s[i];
    		}
    		while (isOperator(s[i]))		//5)如果是运算符,执行算法对应操作;
    		{
    			if (top==0 || stack[top]=='(' || priority(s[i]) > priority(stack[top])) //空栈||或者栈顶为)||新来的元素优先级更高
    			{
    				++top;
    				stack[top] = s[i];
    				break;
    			}
    			else
    			{
    				output[outLen++] = stack[top];
    				output[outLen++] = ' ';
    				--top;
    			}
    		}
    		if (s[i]==')')					//6)假如是开括号,栈中运算符逐个出栈并输出,直到遇到闭括号。闭括号出栈并丢弃。
    		{
    			while (stack[top]!='(')
    			{
    				output[outLen++] = stack[top];
    				output[outLen++] = ' ';
    				--top;
    			}
    			--top;	// 此时stack[top]==')',跳过)
    		}
    		//7)假如输入还未完毕,跳转到步骤2。
    	}
    	while (top!=0)						//8)假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。
    	{
    		output[outLen++] = stack[top];
    		output[outLen++] = ' ';
    		--top;
    	}
    }
    
    double OP(double op1,double op2,char op)
    {
    	double res = 0;
    	if (op=='+')
    		res = op1 + op2;
    	else if (op=='-')
    		res = op1 - op2;
    	else if (op=='*')
    		res = op1 * op2;
    	else if (op=='/')
    		res = op1 / op2;
    	return res;
    }
    
    double cSt1[200];
    double calc(char *s)				//波兰式需要用两个栈,逆波兰式只需要一个栈
    {
    	char dst[80];
    	int top1=0, i;
    	for (i=0; s[i]; ++i)
    	{
    		if (s[i] && s[i] != ' ')
    		{
    			sscanf(s+i,"%s",dst);
    			if (isdigit(dst[0]))
    			{
    				++top1;
    				cSt1[top1] = atof(dst);		//进栈
    			}
    			else
    			{
    				cSt1[top1-1] = OP(cSt1[top1-1], cSt1[top1], dst[0]);
    			//	memcpy(cSt1[top1-1],DstBuf,sizeof DstBuf);
    				--top1;						//操作数栈:出栈俩,进栈一
    			}
    			while (s[i] && s[i] != ' ')
    				++i;
    		}
    	}
    	return cSt1[1];
    }
    int main()
    {
    #ifndef ONLINE_JUDGE
    	freopen("2.txt","r",stdin);
    #endif
    
    	int T = 1;
    	while (gets(input) && strcmp(input,"0"))
    	{
    		rePolish(input, strlen(input));
    
    		output[outLen-1] = '\0';
    //		printf("Case %d:\n%s\n",T++,output);
    		printf("%.2lf\n",calc(output));
    	}
    	return 0;
    }
    //测试用例:1 - 3 + 4


     

    展开全文
  • 波兰式逆波兰式.txt

    2021-04-23 14:38:27
    波兰式逆波兰式.txt
  • C++代码实现逆波兰式

    2021-01-19 23:35:39
    100行以内C++代码实现逆波兰式 逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)。 算术表达式转逆波兰式例子: 逆波兰式整体的算法流程图如下: 下面给出我...
  • 逆波兰式计算器

    2018-06-15 13:21:46
    逆波兰式完整代码计算器,带注释可直接运行VS2013,测试数据"1.0+3/2-tan(45)/(1+1)",
  • 逆波兰式和波兰式

    2021-06-13 17:34:34
    中缀表达式,前缀表达式(波兰式),后缀表达式(逆波兰式) 中缀表达式就是我们常用的形式:1+2*6+1 前缀表达式从右往左扫描,后缀表达式就是从左往右扫描 作用:实现逆波兰式的算法,难度并不大,但为什么要将...

    中缀表达式,前缀表达式(波兰式),后缀表达式(逆波兰式)

    中缀表达式就是我们常用的形式:1+2*6+1
    前缀表达式从右往左扫描,后缀表达式就是从左往右扫描
    作用:实现逆波兰式的算法,难度并不大,但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式?原因就在于这个简单是相对人类的思维结构来说的,对计算机而言中序表达式是非常复杂的结构。相对的,逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序

    此处简要说明一下中缀表达式(原式)转后缀表达式(逆波兰式)的方法。

    构建一个栈,遵循如下规则:

    • 依次扫描,如果是数字,输出到序列;如果是运算符,入栈
    • 如果运算符优先级大于栈中优先级,出栈直到栈中优先级均小于运算符,再把运算符入栈,如果是括号,则找到反括号出栈为止
    /*************************************************************************
    	> File Name: pp.cpp
    	> Author: liuhao
    	> Mail: 2226958871@qq.com
    	> Created Time: Sun 13 Jun 2021 08:55:41 PM CST
     ************************************************************************/
    
    #include <iostream>
    #include <stack>
    #include <string>
    #include <cctype>
    
    std::string bolan();
    int getdata(char);
    int getnum(std::string);
    
    int main() {
        std::string str = bolan();
        int n = getnum(str);
        std::cout << n << std::endl;
        return 0;
    }
    
    int getdata(char s) {
        if (s == '*' || s == '/') {
            return 1;
        }
        else if (s == '+' || s == '-') {
            return 0;
        }
        return -1;
    }
    
    std::string bolan() {
        using std::cout, std::endl, std::cin, std::string, \
            std::stack;
        string input_str;
        cin >> input_str;
        string output_str;
        int n = 1;
        stack<char> s_operator;
        for (int i = 0; i < input_str.size(); ++i) {
            if (isdigit(input_str[i])) {
                output_str.push_back(input_str[i]);
            }
            else {
                if (!s_operator.empty()) {
                    while (!s_operator.empty() && (getdata(s_operator.top()) >= getdata(input_str[i]))) {
                        output_str.push_back(s_operator.top());
                        s_operator.pop();
                    }
                }
                else {
                    n += 1;
                }
                s_operator.push(input_str[i]);
            }
        }
        while (!s_operator.empty()) {
            char a = s_operator.top();
            s_operator.pop();
            output_str.push_back(a);
        }
        return output_str;
    }
    
    int getnum(std::string str) {
        std::stack<int> s_num;
        for (int i = 0; i < str.size(); ++i) {
            if (isdigit(str[i])) {
                s_num.push(str[i] - '0');
            }
            else {
                int f1 = s_num.top();
                s_num.pop();
                int f2 = s_num.top();
                s_num.pop();
                int num;
                if (str[i] == '*') {
                    num = f1*f2;
                }
                else if (str[i] == '-') {
                    num = f1-f2;
                }
                else if (str[i] == '+') {
                    num = f1+f2;
                }
                else if (str[i] == '/') { 
                    num = f1/f2;
                }
                s_num.push(num);
            }
        }
        return s_num.top();
    }
    

    在这里插入图片描述

    展开全文
  • 介绍了C语言实现逆波兰式实例,有需要的朋友可以参考一下
  • C++实现逆波兰式

    2020-12-16 21:34:08
    (a+b)c的逆波兰式为ab+c,假设计算机把ab+c按从左到右的顺序压入栈中,并且按照遇到运算符就把栈顶两个元素出栈,执行运算,得到的结果再入栈的原则来进行处理,那么ab+c的执行结果如下: 1)a入栈(0位置) 2)b...
  • 波兰式和逆波兰式

    千次阅读 2015-03-10 11:26:00
    波兰式和逆波兰式例子

    遍历二叉树的口诀

    1,先序遍历:根-左-右

    2,中序遍历:左-根-右

    3,后续遍历:左-右-根


    数学表达式  a+b*(c-d)-e/f

    首先画出该表达式对应的二叉树


    根据二叉树分别写出

    先序遍历-+a*b-cd/ef      这就是表达式的前缀表示也就是波兰式

    中序遍历a+b*c-d-e/f      这就是表达式的中缀表示

    后序遍历abcd-*+ef/-      这就是表达式的后缀表示也就是逆波兰式


    展开全文
  • 逆波兰式代码

    2014-04-07 17:30:34
    逆波兰式,c语言,适合新手,老师让交的作业
  • 主要介绍了PHP使用逆波兰式计算工资的方法,实例分析了php逆波兰式算法的原理与相关使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 栈实现逆波兰式

    2017-04-15 16:29:00
    表达式由单字母变量和双目四则运算符及“(” 和“)” 组成,设计算法求表达式的逆波兰式
  • 将一个中缀表达式转换成后缀表达式(逆波兰式),用到了堆栈的数据结构。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,595
精华内容 2,238
关键字:

逆波兰式