精华内容
下载资源
问答
  • 后缀算术表达式(逆波兰式)的函数算法思想: //中缀算术表达式->后缀算术表达式(逆波兰式) //前缀表达式是波兰式 //刚开始做的时候是把单个字符char作为栈的元素类型,但这样的话不能对>=10的数以及小数...

    中缀算术表达式->后缀算术表达式(逆波兰式(不含括号))的函数算法思想:
    在这里插入图片描述

    链接:逆波兰式的百度百科

    逆波兰式求值的算法思想:
    栈S存放逆波兰式,现开辟栈S1、S2,S1存放S的逆置
    然后每次弹出S1的栈顶元素e,若为操作数,则直接将e压入栈S2中;若为运算符,则弹出S2的两个元素e1、e2,然后进行运算(即e1 e e2(e1、e2为操作数,e为运算符)),然后将运算结果重新压入栈S2中,一直循环,直至S1为空循环结束
    链接:csdn—逆波兰式求值

    //中缀算术表达式->后缀算术表达式(逆波兰式)
    //前缀表达式是波兰式
    
    //刚开始做的时候是把单个字符char作为栈的元素类型,但这样的话不能对>=10的数以及小数进行操作
    //所以最后把栈的元素类型改为string,输入空格作为单次cin的停止,进而将string存入栈中
    
    //最终目的:可以测试>=10的数以及小数(已完成,使用了string作为栈的元素类型,
    //不过需要注意的是string与string输入的时候之间要有空格作为两者的分割)
    
    #include<iostream>
    #include<cctype>//包含isdigit()函数
    #include<cstdlib>//包含atof函数
    //to_string()函数是全局函数
    using namespace std;
    #define SElemType string
    typedef struct SNode
    {
        SElemType data;
        struct SNode* prior,* next;
    }SNode,* Slink;
    
    typedef struct
    {
        Slink head,tail;
        int length;
    }Stack;
    
    bool Init_Stack(Stack& S)
    {
        S.head=S.tail=new SNode;
        if(!S.head) exit(-2);
        S.head->next=S.head->prior=nullptr;
        S.length=0;
        return true;
    }
    
    bool IsEmpty(Stack S)
    {
        if(!S.length) return true;
        return false;
    }
    
    SElemType GetTop(Stack S)
    {
        if(IsEmpty(S)) exit(-1);
        return S.tail->data;
    }
    
    bool Push(Stack& S,SElemType e)
    {
        Slink p=new SNode;
        if(!p) return false;
        p->data=e;
        p->next=nullptr;
        S.tail->next=p;p->prior=S.tail;
        S.tail=p;
        S.length++;
        return true;
    }
    
    bool Pop(Stack& S,SElemType& e)
    {
        if(IsEmpty(S)) return false;
        Slink p=S.tail;
        S.tail=S.tail->prior;
        S.tail->next=nullptr;
        e=p->data;
        delete p;
        S.length--;
        return true;
    }
    
    void Output_Stack(Stack S)
    {
        cout<<"逆波兰式:\n";
        cout<<"----"<<endl;
        Slink p=S.tail;
        while(p->prior){
            cout<<p->data<<endl;
            p=p->prior;
        }
        cout<<"----"<<endl;
    }
    //上述函数为栈的基本操作
    
    bool IsOpnd(string str)//str是操作数(即str是数字串),返回true
    {
        if(isdigit(str[0]))//若是数字字符
            return true;
        return false;
    }
    
    bool IsOper(string str)//str是算术运算符,返回true
    {
        if(str[0]=='+'||str[0]=='-'||str[0]=='*'||str[0]=='/') return true;
        return false;
    }
    
    int Locate(string str)
    {
        switch(str[0])
        {
            case '+':return 0;
            case '-':return 1;
            case '*':return 2;
            case '/':return 3;
            case '(':return 4;
            case ')':return 5;
            case '#':return 6;
        }
    }
    
    int PriorityCompare(string str1,string str2)//ch1为栈顶元素字符,ch2为刚输入的字符
    //优先性:ch1>ch2,return 1;ch1==ch2,return 0;ch1<ch2,return -1
    //Poriority二维数组是优先性级别表,行对应str1,列对应str2
    {
        int i=Locate(str1),j=Locate(str2);
        int Poriority[7][7]={{1,1,-1,-1,-1,1,1},{1,1,-1,-1,-1,1,1},{1,1,1,1,-1,1,1}
        ,{1,1,1,1,-1,1,1},{-1,-1,-1,-1,-1,0,2},{1,1,1,1,2,1,1},{-1,-1,-1,-1,-1,2,0}};
        return Poriority[i][j];
    }
    
    SElemType Operater(string str1,string op,string str2)//返回str1 op str2的string型结果
    {
        double e1=atof(str1.c_str()),e2=atof(str2.c_str()),result;//get到str1,str2的double型
        switch(op[0])//运算
        {
            case '+':result=e1+e2;break;
            case '-':result=e1-e2;break;
            case '*':result=e1*e2;break;
            case '/':result=e1/e2;break;
        }
        return to_string(result);//返回结果的string型数据
    }
    
    SElemType GetRPNValue(Stack S)//返回逆波兰式的值,结束后S已被破坏
    {
        Stack S1,S2;//辅助栈 将S的元素逆置放到栈S1中,栈S2计算结果
        Init_Stack(S1);
        Init_Stack(S2);
        SElemType e;
        while(!IsEmpty(S)){
            Pop(S,e);
            Push(S1,e);
        }//逆置完成
        while(!IsEmpty(S1)){
            Pop(S1,e);
            if(IsOpnd(e))//若是操作数
                Push(S2,e);
            if(IsOper(e)){//若是运算符,弹出两个操作数进行运算
                SElemType e1,e2;
                Pop(S2,e2);
                Pop(S2,e1);
                Push(S2,Operater(e1,e,e2));
            }
        }
        return GetTop(S2);//最后栈顶存放着结果
    }
    
    bool GetRPN()//得到逆波兰式
    {
        Stack S1,S2;
        Init_Stack(S1);Init_Stack(S2);
        Push(S1,"#");
        string str;
        SElemType e;
        cout<<"输入多个string型字符串,至#停止\n需要注意的是:cin遇到空格停止,你可以这样输入:( 1.2 + 3 )\n";
        while(cin>>str,str!="#"){//cin遇到空白字符,该次输入停止;但循环还没结束
            if(IsOpnd(str)){//str是操作数
                Push(S2,str);
            }
            if(IsOper(str)){//str是算术运算符
                if(PriorityCompare(GetTop(S1),str)==1||!PriorityCompare(GetTop(S1),str)){//若栈顶元素的优先性大于/等于str
                    while(PriorityCompare(GetTop(S1),str)==1||!PriorityCompare(GetTop(S1),str)){
                        Pop(S1,e);
                        Push(S2,e);
                    }//循环至栈顶元素的优先性小于str为止
                    Push(S1,str);//将str压入栈S1中
                }
                else if(PriorityCompare(GetTop(S1),str)==-1)//若栈顶元素的优先性小于str
                    Push(S1,str);
            }
            if(str[0]=='(')//str是"("
                Push(S1,str);
            if(str[0]==')'){//str是")"
                while(GetTop(S1)[0]!='('){
                    Pop(S1,e);
                    Push(S2,e);
                }
                Pop(S1,e);//栈S1的"("和")"之间的元素已经移动到S2中,现将")"对应的"("从栈S1中弹出
            }
        }//至此str=="#"
        //需要将 栈底'#'与新输入的#的栈S1之间的string字符串 移到栈S2中
        while(!IsEmpty(S1)&&GetTop(S1)[0]!='#'){
            Pop(S1,e);
            Push(S2,e);
        }
        Output_Stack(S2);
        cout<<"对该逆波兰式求值:"<<GetRPNValue(S2)<<endl;
        return true;
    }
    
    int main()
    {
        GetRPN();
        return 0;
    }
    
    
    输入多个string型字符串,至#停止
    需要注意的是:cin遇到空格停止,你可以这样输入:( 1.2 + 3 )
    ( 1.2 + 10 ) * 1.1 - ( 1.2 + 10 ) / 3 #
    ----
    -
    /
    3
    +
    10
    1.2
    *
    1.1
    +
    10
    1.2
    ----
    对该逆波兰式求值:8.586667
    
    Process returned 0 (0x0)   execution time : 18.136 s
    Press any key to continue.
    
    
    展开全文
  • 逆波兰表达式求值

    2019-11-09 13:59:11
    逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后) 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 说明: 整数除法只...

    flag

    软件学院大三党,每天一道算法题,第30天

    题目介绍

    根据逆波兰表示法,求表达式的值。
    逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)

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

    整数除法只保留整数部分。
    给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation

    思路

    仔细观察这个tokens数组,每个运算符之前一定有至少两个数字,数组最后一定是运算符
    我们采用一个装整数的栈,遍历这个数组,当遇到数字的时候,将数字入栈,当遇到运算符的时候,将栈顶的两个元素出栈,经过运算后的数字再入栈。

    关键代码

        public static int evalRPN(String[] tokens){
            Stack<Integer> stack=new Stack();
            int len=tokens.length;
            int result=0;
            for(int i=0;i<len;i++){
                if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
                    int x1=stack.pop();
                    int x2=stack.pop();
                    int x3;
                    if(tokens[i]=="+")
                        x3=x2+x1;
                    else if(tokens[i]=="-")
                        x3=x2-x1;
                    else if(tokens[i]=="*")
                        x3=x2*x1;
                    else
                        x3=x2/x1;
                    stack.push(x3);
                }
                else {
                    stack.push(Integer.parseInt(tokens[i]));
                }
    
            }
            return stack.pop();
        }
    
    展开全文
  • 首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入逆波兰式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定...

    leecode150.逆波兰表达式求值

    题目

    在这里插入图片描述

    算法实现

    将一个普通的中序表达式转换为逆波兰表达式的一般算法是:
    首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入逆波兰式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定非#不可。从中缀式的左端开始取字符,逐序进行如下步骤:
    (1)若取出的字符是操作数,则分析出完整的运算数,该操作数直接送入S2栈
    (2)若取出的字符是运算符,则将该运算符与S1栈栈顶元素比较,如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级,则将该运算符进S1栈,否则,将S1栈的栈顶运算符弹出,送入S2栈中,直至S1栈栈顶运算符低于(不包括等于)该运算符优先级,最后将该运算符送入S1栈。
    (3)若取出的字符是“(”,则直接送入S1栈顶。
    (4)若取出的字符是“)”,则将距离S1栈栈顶最近的“(”之间的运算符,逐个出栈,依次送入S2栈,此时抛弃“(”。
    (5)重复上面的1~4步,直至处理完所有的输入字符
    (6)若取出的字符是“#”,则将S1栈内所有运算符(不包括“#”),逐个出栈,依次送入S2栈。

    代码实现

    template<typename T>
    class MyStack
    {
    public:
    	MyStack(int size);
    	int stackSize();
    	void Enstack(T x);
    	bool Destack();
    	T Behind();
    	bool IfEmpty();
    	~MyStack();
    
    private:
    	T* data;
    	int rear;
    };
    
    
    
    template<typename T>
    int MyStack<T>::stackSize()
    {
    	return rear + 1;
    }
    
    template<typename T>
    bool MyStack<T>::IfEmpty()
    {
    	if (rear < 0)
    		return true;
    	else
    		return false;
    }
    
    template<typename T>
    bool MyStack<T>::Destack()
    {
    	if (IfEmpty())
    		return false;
    	rear = (rear - 1);
    	return true;
    }
    
    template<typename T>
    void MyStack<T>::Enstack(T x)
    {
    	rear = (rear + 1);
    	data[rear] = x;
    }
    
    template<typename T>
    T MyStack<T>::Behind()
    {
    	if (IfEmpty())
    		return 0;
    	T temp = data[rear];
    	return temp;
    }
    
    template<typename T>
    MyStack<T>::~MyStack()
    {
    	delete[] data;
    }
    
    
    
    		for (int i = 0; i < tokens.size(); i++)
    		{
    			if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/")
    				stk.Enstack(atoi(tokens[i].c_str()));
    			else
    			{
    				int cal = 0;
    				cal = tokens[i][0];
    				temp_sec = stk.Behind();
    				stk.Destack();
    				temp_first = stk.Behind();
    				stk.Destack();
    				switch (cal)
    				{
    				case 43:
    					stk.Enstack(temp_first + temp_sec);
    					break;
    				case 45:
    					stk.Enstack(temp_first - temp_sec);
    					break;
    				case 42:
    					stk.Enstack(temp_first * temp_sec);
    					break;
    				case 47:
    					stk.Enstack(temp_first / temp_sec);
    					break;
    				}
    			}
    		}
    		return stk.Behind();
    	}
        }
    };
    
    展开全文
  • 用递归解决递归形式问题...(郭炜老师:其实这里应该叫波兰表达式,逆波兰表达式为符号在后面的子) 输入: 输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点 数 输出: 输出为一行,表达式的。 样例输

    用递归解决递归形式问题
    例题:逆波兰表达式
    逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2+3的逆波兰表示法为+2 3。逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2+3) * 4的逆波兰表示法为+2 3 4。本题求解逆波兰表达式的值,其中运算符包括+ - * / 四个。
    (郭炜老师:其实这里应该叫波兰表达式,逆波兰表达式为符号在后面的式子)
    输入:
    输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点

    输出:
    输出为一行,表达式的值。
    样例输入:

    *+11.0 12.0 +24.0 35.0
    

    样例输出:
    1357.000000
    提示:(11.0+12.0)*(24.0+35.0)

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    double exp()
    {
    	char s[20];
    	cin >> s;
    	switch(s[0])
    	{
    		case '+': 
    			return exp() + exp();
    		case '-': 
    			return exp() - exp();
    		case '*': 
    			return exp() * exp();
    		case '/': 
    			return exp() / exp();
    		default:
    			return atof(s);		//atof将字符浮点数转化成double类型
    			break;
    	}
    }
    
    int main() 
    {
    	printf("%lf",exp());
    	return 0;
    }
    
    展开全文
  • 文章目录一、前言二、表达式1.中缀表达式1.1 定义2.前缀表达式2.1 定义2.2 求值3....逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式...
  • 后缀表达式就是标题所说的逆波兰表达式,和我们平时把运算符号位于操作数之间不同,后缀表达式将运算符置于操作数之后。 举例说明:6-1+3*2 = 11就是一个中缀表达式。 对应的波兰式,即前缀表达式为:[’-’, ‘6’...
  • 题目描述 根据逆波兰表示法,表达式的。 有效的运算符包括 +, -, *, / 。...只要明白了“逆波兰式”其实就是一个表达式的后缀表示,然后再用一个栈就可以实现算法了(其实实现起来还是比较麻烦的)。例如: ...
  • 逆波兰式 http://www.cnblogs.com/youxin/archive/2012/07/30/2615716.html 逆波兰式也叫后缀表达式(postfix)(将运算符写在操作数之后),相应的波兰表达式叫前缀表达式(运算符在操作数之前)。 中缀表达式...
  • 实现逆波兰式算法,难度并不大,但为什么要将看似简单的中序表达式转换为复杂的逆波兰式?原因就在于这个简单是相对人类的思维结构来说的,对计算机而言中序表达式是非常复杂的结构。相对的,逆波兰式在计算机看来...
  • ########################################################## ...# a:算法:先逆波兰表达式,然后计算逆波兰表达式 # b:数据结构:采用数组保存(用数组模拟栈) # #脚本说明: #脚本名:rpn.sh #脚本
  • leetcode之逆波兰求值

    2014-05-14 20:02:41
    首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入逆波兰式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定...
  • 栈:逆波兰式

    千次阅读 2017-07-10 12:08:59
    试利用栈实现一个算法,将一个通常书写形式且书写正确的表达式转换为逆波兰式(后缀表达式),同时将转换后的逆波兰式求值,最后仅需输出求值结果。 输入格式 输入共有一行,为待求值的表达式,以换行结束。表达式...
  • 一、把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符,对于不同类型的字符按不情况进行处理。1、先定义一个工作数组,用来存储转换之后的后缀表达式,定义一个栈,用来存储...
  • 参照leno_a大牛的代码自己练习了一遍中缀转后缀的算法,写个类自用 package javatestcode; import java.math.BigDecimal; import java.util.ArrayList; import java.util.Iterator; import java.util....
  • 逆波兰表达式算法

    万次阅读 2012-11-17 01:02:37
    通过逆波兰表达式一个计算子的,也是很简单的,只要遇到过会用就行了。 1、将一个中序表达式转化成为逆波兰表达式。  首先维护的是两个栈,我们这里暂且称为S1和S2,S1中的结果最后存的就是逆波兰表达式,S2...
  • /**********************************************...一、把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符,对于不同类型的字符按不情况进行处理。 1、先定义一个工作数组,用来存
  • 表达式求值的经典算法(逆波兰) 数据表达式类 1. 可完成中缀表达式到后缀表达式的转换 2. 后缀表达式求值.
  • (1)设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达 。 (2)设计两个栈 S1、S2 都采用顺序栈方式,并且共享一个存储区[0,MaxLen-1], 为了尽量利用空间,减少溢出的可能,可采用栈顶...
  • 而计算机更加习惯“后缀式”(也叫“逆波兰式”,Reverse Polish Notation)。上述中缀式对应的后缀式是: 3 5 2 * + 现在,请对输入的后缀式进行求值。 输入格式: 在一行中输入一个后缀式,运算数和运算符之间用...
  • 试利用栈实现一个算法,将一个通常书写形式且书写正确的表达式转换为逆波兰式(后缀表达式),同时将转换后的逆波兰式求值,最后输出逆波兰式及最终的求值结果。 输入格式 输入共有一行,为待求值的表达式,以换行...
  • 文章目录题目:分析实现...而计算机更加习惯“后缀式”(也叫“逆波兰式”,Reverse Polish Notation)。上述中缀式对应的后缀式是: 3 5 2 * + 现在,请对输入的后缀式进行求值。 输入格式: 在一行中输入一...
  • 逆波兰表达式

    2016-03-29 09:00:57
    通过逆波兰表达式一个计算子的,也是很简单的,只要遇到过会用就行了。 1、将一个中序表达式转化成为逆波兰表达式。  首先维护的是两个栈,我们这里暂且称为S1和S2,S1中的结果最后存的就是逆波兰...
  • 逆波兰表达式总结

    2013-08-05 11:18:50
    通过逆波兰表达式一个计算子的,也是很简单的,只要遇到过会用就行了。 1、将一个中序表达式转化成为逆波兰表达式。  首先维护的是两个栈,我们这里暂且称为S1和S2,S1中的结果最后存的就是逆波兰表达式,S2...
  • 题目在这里》 题意:给你一个中序表达式,由(、)、+、-、*以及a-z的小写字母组成,其中有n个不同的小写字母表示n个未知数,再给n个数分别表示这n个...先来复习一下将一个中序表达式转化为逆波兰式算法: 1:准
  • 【经典算法】-算术表达式求值

    万次阅读 多人点赞 2017-09-28 18:20:37
    算术表达式求值 中缀表达式 我们平时写的计算子一般是这样子 格式:"操作数1 操作符 操作数2" 12 * (3 + 4) - 6 + 8 / 2; // 中缀表达式 中缀表达式如果要先计算操作符优先级低的两个数,比如上面...
  • 文章目录基本理解中缀表达式转化为前缀表达式1,算法描述2,实例3,用前缀表达式的求值4,前缀表达式的计算机求值中缀表达式转化为后缀表达式1,算法描述2,实例3,用后缀表达式的求值4, 后缀表达式的计算机求值 ...
  • 计算逆波兰式(后缀表达式)的 运算符仅包含"+","-","*“和”/",被操作数可能是整数或其他表达式 例如: [“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9 [“4”, “13”, “5”, “/”, “+...
  • 为什么要将看似简单的中序表达式转换为复杂的逆波兰式? 栈和表示式求值 算法思想: 编程要求 测试说明 任务描述 本关任务:编写一个能根据逆波兰表示法,求表达式的值的程序。 相关知识 为了完成本关任务,你需要...

空空如也

空空如也

1 2 3
收藏数 54
精华内容 21
关键字:

逆波兰式求值算法