精华内容
下载资源
问答
  • 【算法】表达式值--逆波兰算法介绍 转自:https://www.cnblogs.com/lulipro/p/7450886.html 逆波兰算法介绍 假定给定一个只 包含 加、减、乘、除,和括号的算术表达式,你怎么编写程序计算出其结果? 问题...

    【算法】表达式求值--逆波兰算法介绍

    转自:https://www.cnblogs.com/lulipro/p/7450886.html

    逆波兰算法介绍

    假定给定一个只 包含 加、减、乘、除,和括号的算术表达式,你怎么编写程序计算出其结果?

    问题是:在表达式中,括号,以及括号的多层嵌套 的使用,运算符的优先级不同等因素,使得一个算术表达式在计算时,运算顺序往往因表达式的内容而定,不具规律性。 这样很难编写出统一的计算指令。
    使用逆波兰算法可以轻松解决这个问题。他的核心思想是将普通的中缀表达式转换为后缀表达式。

    什么是中缀表达式?例如a+b,运算符在两个操作数的中间。这是我们从小学开始学习数学就一直使用的表达式形式。

    什么是后缀表达式?例如a b + ,运算符在两个操作数的后面。后缀表达式虽然看起来奇怪,不利于人阅读,但利于计算机处理。

    转换为后缀表达式的好处是:


    1、去除原来表达式中的括号,因为括号只指示运算顺序,不是实际参与计算的元素。
    2、使得运算顺序有规律可寻,计算机能编写出代码完成计算。

     

    算术表达式的组成部分

    一个表达式有如下及部分元素组成

    • 操作数:可以是任何数值:1,89 , 3.14159 ...
    • 运算符:

      分为单目运算符 如 sin , cos , 双目运算符 如 加、减、乘、除 。

      运算符还会分为左结合性和右结合性。同级的左结合性的运算符从左往右依次计算。同级的右结合性的运算符从右往左依次计算。 
      如: 7-6+1 等价于 (7-6) + 1 ,因为普通加减运算符是左结合性的。
      如:C语言中的组合赋值语句: a = b = 1 等价于 a = (b=1) ,因为赋值运算符在C中是右结合性的。

           对于单目运算符,还分为前缀运算符和后缀运算符,如 sin(x) 是前缀运算符,而 阶乘运算符 : n ! 就是后缀运算符。

    • 分界符:一般是圆括号 ( ) , 用于指示运算的先后顺序。

    在本文中,只会考虑算术表达式 有 加、减、乘、除 运算符, 左右圆括号 ( , ) ,以及合法的数字简单的情况。对于更加复杂的运算符,只要对这个算法轻微修改,就可以支持。

     

    逆波兰算法的原理

    逆波兰算法的核心步骤就2个:
    1、将中缀表达式转换为后缀表达式,例如输入的原始表达式是 3*(5+7) ,转换得到 3 5 7 + *
    2、根据后缀表达式,按照特定的计算规则得到最终计算结果

    下面详细介绍这个2步的操作。

    中缀表达式转换为后缀表达式
    你需要设定一个栈SOP,和一个线性表 L 。SOP用于临时存储运算符和左括号分界符( ,L用于存储后缀表达式。
    遍历原始表达式中的每一个表达式元素
    (1)如果是操作数,则直接追加到 L中。只有 运算符 或者 分界符( 才可以存放到 栈SOP中
    (2)如果是分界符
             Ⅰ 如果是左括号 ( , 则 直接压入SOP,等待下一个最近的 右括号 与之配对。
              Ⅱ 如果是右括号),则说明有一对括号已经配对(在表达式输入无误的情况下)。不将它压栈,丢弃它,然后从SOP中出栈,得到元素e,将e依次追加到L里。一直循环,直到出栈元素e 是 左括号 ( ,同样丢弃他。
    (3)如果是运算符(用op1表示)
            Ⅰ如果SOP栈顶元素(用op2表示) 不是运算符,则二者没有可比性,则直接将此运算符op1压栈。 例如栈顶是左括号 ( ,或者栈为空。
             Ⅱ 如果SOP栈顶元素(用op2表示) 是运算符 ,则比较op1和 op2的优先级。如果op1 > op2 ,则直接将此运算符op1压栈。
    如果不满足op1 > op2,则将op2出栈,并追加到L,重复步骤3。
    也就是说,如果在SOP栈中,有2个相邻的元素都是运算符,则他们必须满足:下层运算符的优先级一定小于上层元素的优先级,才能相邻。

    最后,如果SOP中还有元素,则依次弹出追加到L后,就得到了后缀表达式。

    伪代码:

    #将参数中缀表达式expression转为后缀表达式存放在L中,返回L
    function infixToSuffix(expression):
    {
        for each element in expression        #对表达式中的每一个元素
        {
            if (element 是一个操作数)
            {
                L.append(element)             #将这个元素追加到线性表L后
            }
    
            else if (element 是 一个运算符)
            {
                While (sop栈 不为空  &&  sop栈顶元素 是一个运算符  && element的优先级 <= sop栈顶运算符元素的优先级 )
                {
                    L.append(sop.pop())
                }
                sop.push(element);     
            }
    
            else if(element 是 一个分界符)
            {
                if (element is  '('  )
                {
                    sop.push(element)
                }
                else if( element is  ')'  )
                {
                    While (sop栈不为空 &&   sop栈顶元素 不是 '('  )    #将匹配的2个括号之间的栈元素弹出,追加到L
                    {
                        L.append( sop.pop() ); 
                    }
                    if(sop栈不为空 )
                    {
                        sop.pop()           #将匹配到的 '(' 弹出丢弃
                    }
                }
            }
    
        }
    
        While (sop 栈 不为空)       #将sop栈中剩余的所有元素弹出,追加到L后
        {
            L.append(sop.pop())
        }
    
        return L
    }

    示例图:

     

     

    根据后缀表达式计算得到最终结果

     

    执行这步操作时,也需要一个栈scalc,用于存放计算中的操作数。

    伪代码:

    function suffixToResult(suffix_expression)
    {
        for each element in suffix_expression
        {
            if(element 是 操作数)
            {
                scalc.push(element)
            }
            else if(element 是运算符)
            {
                #从栈中弹出2个操作数 num1 和 num2 。注意:后弹出的num2是第一操作数,num1是第二操作数 。
                #因为这里考虑的都是二元运算符,因此需要弹2个元素出来进行运算。
                num1 = scalc.pop()
                num2 = scalc.pop()
    
                #使用element代表的运算符完成 num2 和 num1 的计算,产生临时结果 temp_value
                temp_value = num2 【element的运算符: +  ,-  ,* , / 】 num1
    
                #将temp_value压栈
                scalc.push(temp_value)   
            }
    
            #如果一切正常,最后栈scalc中仅仅只有一个元素,这个元素就是最终的结果
            return sclac.pop()
        }
    }

     

    示例图

     

    代码实现(Java)

    1、核心算法实现是 InfixExpression类中的   public SuffixExpression toSuffixExpression()  和 SuffixExpression  类中的  double getResultValue() throws Exception 。

    2、并没有实现解析输入的代码,因此算术表达式只能通过硬编码构造。涉及到编译原理的知识,书到用时方恨少,哎。

    3、所有的操作数内部使用double存储。

     

    package com. lulix86 .calc ;
    
    import java. util .ArrayList ;
    import java. util .Deque ;
    import java. util .HashMap ;
    import java. util .Iterator ;
    import java. util .LinkedList ;
    import java. util .List ;
    import java. util .Map ;
    import java. util .regex . Matcher;
    import java. util .regex . Pattern;
    
    public class App
    {
    
          public static void main (String [] args )
          {
    
                InfixExpression expression = new InfixExpression () ;
    
                //   (1+8)-(3*(4-1))  = 0
    
                expression .append ( "(") ;
                expression .append ( "1") ;
                expression .append ( "+") ;
                expression .append ( "8") ;
                expression .append ( ")") ;
                expression .append ( "-") ;
                expression .append ( "(") ;
                expression .append ( "3") ;
                expression .append ( "*") ;
                expression .append ( "(") ;
                expression .append ( "4") ;
                expression .append ( "-") ;
                expression .append ( "1") ;
                expression .append ( ")") ;
                expression .append ( ")") ;
    
    
                System . out. println( "原始表达式:" + expression );
    
                try
                {
                     System . out. println( "计算结果是:" + expression. getResultValue () ) ;
                } catch (Exception e)
                {
    
                     System . out. println( "一定是表达式输入的有问题,请检查后重试" ) ;
                }
    
    
          }
    
    
    }
    
    /**
     * 表达式元素的公父类。表达式元素具体分为:运算符类,操作数类,分界符类。因此这个类有3个子类。 这是一个抽象类。 这个类的作用如下:
     * 1、定义了表达式元素的共同属性:String content,用来存储元素的字符串形式的内容。
     * 2、限定了分界符元素和运算符元素的相关性质:如可取的content值,运算符的优先级等。
     * 2、这个类提供了一些供子类使用的工具函数:isLegalXXXX。
     *
     *
     * @see ExpressionDelimeter
     * @see ExpressionOperator
     * @see ExpressionOperand
     *
     */
    abstract class ExpressionElement
    {
    
          // -----------------------------分界符-----------------------------------
    
          // 表达式中的分界符:左右圆括号
          public static final String LEFT_PARENTHESES = "(" ;
          public static final String RIGHT_PARENTHESES = ")" ;
    
          protected static boolean isLegalDelimeter (String content)
          {
                if ( LEFT_PARENTHESES .equals ( content) || RIGHT_PARENTHESES . equals( content ))
                     return true ;
                return false ;
          }
    
          // -----------------------------运算符-----------------------------------
          // 运算符:这里只用到了常见的这4个运算符
          public static final String PLUS = "+" ;
          public static final String MINUS = "-" ;
          public static final String MULTIPLE = "*" ;
          public static final String DIVIDE = "/" ;
    
          // 将运算符 和 他的 优先级 通过 k-v 对存放到 Map中:运算符的优先级分为2个等级,用数字1 和2代表,数值越大,优先级越高
          protected static final Map <String , Integer> operatorPiority = new HashMap <> ();
          static
          {
                operatorPiority .put ( PLUS, 1) ;
                operatorPiority .put ( MINUS, 1) ;
                operatorPiority .put ( MULTIPLE, 2) ;
                operatorPiority .put ( DIVIDE, 2) ;
          }
    
          protected static boolean isLegalOperator (String content)
          {
                if ( ! operatorPiority. containsKey (content ))
                     return false ;
                return true ;
          }
    
          // -----------------------------操作数-----------------------------------
          // 通过正则表达式校验一个字符串是否是合法的数字 。
          protected static boolean isLegalOperand (String content)
          {
                Pattern numberPat = Pattern .compile ( "(\\+|-)?(\\d+\\.)?\\d+" );
                Matcher mat = numberPat .matcher ( content) ;
                if ( ! mat. matches ())
                     return false ;
    
                return true ;
          }
    
          protected final String content ;
    
          protected ExpressionElement ( String content )
          {
                this .content = content ;
          }
    
          public String getContent()
          {
                return content ;
          }
    
          @Override
          public String toString()
          {
                return content . toString() ;
          }
    
    }
    
    /**
     * 表达式运算符类。 构造函数私有,不可以自己创建实例,只能用类中预定义的4个静态类对象,分别代表了加减乘除4个运算符。 类对象不可变。
     * 实现了Comparable接口,compareTo方法用来比较2个运算符的优先级。
     *
     */
    
    class ExpressionOperator extends ExpressionElement implements Comparable <ExpressionOperator >
    {
    
          public static final ExpressionOperator OP_MINUS = new ExpressionOperator (ExpressionElement . MINUS) ;
          public static final ExpressionOperator OP_PLUS = new ExpressionOperator (ExpressionElement . PLUS) ;
          public static final ExpressionOperator OP_MULTIPLE = new ExpressionOperator (ExpressionElement . MULTIPLE) ;
          public static final ExpressionOperator OP_DEVIDE = new ExpressionOperator (ExpressionElement . DIVIDE) ;
    
          // -----------------------------------------------------
    
          private final int priority ; // 运算符的优先级
    
          // 不可以在类外实例化运算符,不允许创建其它的新的运算符
          private ExpressionOperator ( String content )
          {
                super (content ) ;
    
                if ( ! isLegalOperator( content ))
                     throw new IllegalArgumentException( "运算符 " + content + " 不是合法的" );
    
                this .priority = operatorPiority .get ( content) ;
          }
    
          public int getPriority()
          {
                return priority ;
          }
    
          @Override
          public int compareTo( ExpressionOperator other )
          {
                return this . priority - other . priority;
          }
    
          @Override
          public boolean equals( Object obj )
          {
                if ( obj == null)
                     return false ;
                if ( obj == this)
                     return true ;
                if ( obj .getClass () != this. getClass ())
                     return false ;
    
                ExpressionOperator other = ( ExpressionOperator) obj;
    
                return this . getContent() . equals( other .getContent ()) ;
          }
    
    }
    
    /**
     * 表达式操作数类。
     *
     * 使用double作为数字的存储类型。 不可变类型。 实现了Comparable接口,compareTo方法用来比较2个操作数的大小。
     *
     * 因为操作数是不可枚举的,因此这个类可以创建实例。
     */
    class ExpressionOperand extends ExpressionElement implements Comparable <ExpressionOperand >
    {
    
          private final double value ;
    
          public ExpressionOperand ( String content )
          {
                super (content ) ;
                try
                {
                     value = Double. parseDouble (content ) ;
                } catch (NumberFormatException e)
                {
                     throw new IllegalArgumentException( content + " 不是一个合法的数字" );
                }
          }
    
          public ExpressionOperand ( double value )
          {
                super (Double . toString( value ));
                this .value = value ;
          }
    
          public double getValue()
          {
                return value ;
          }
    
          @Override
          public int compareTo( ExpressionOperand other )
          {
                return Double . compare( this .value , other . value) ;
          }
    
          @Override
          public String toString()
          {
                return Double . toString( this .value ) ;
          }
    }
    
    /**
     * 表达式分界符类。 不可变类型。 构造函数私有,不可以自己创建实例,只能用类中预定义的2个静态类对象,分别代表左,右括号。
     *
     */
    class ExpressionDelimeter extends ExpressionElement
    {
    
          public static final ExpressionDelimeter DM_LEFT_PARENTHESES = new ExpressionDelimeter (
                     ExpressionElement . LEFT_PARENTHESES) ;
          public static final ExpressionDelimeter DM_RIGHT_PARENTHESES = new ExpressionDelimeter (
                     ExpressionElement . RIGHT_PARENTHESES) ;
    
          private ExpressionDelimeter ( String content )
          {
                super (content ) ;
                if ( ! isLegalDelimeter( content ))
                     throw new IllegalArgumentException( "分界符 " + content + " 不是合法的" );
          }
    
          @Override
          public boolean equals( Object obj )
          {
                if ( obj == null)
                     return false ;
                if ( obj == this)
                     return true ;
                if ( obj .getClass () != this. getClass ())
                     return false ;
    
                ExpressionDelimeter other = ( ExpressionDelimeter) obj ;
    
                return content . equals( other .content ) ;
          }
    
    }
    
    /**
     * 表达式类。 你可以把这个类看做是一个存储表达式元素的线性表,因此可以使用appendXXX方法来构造一个表达式。
     *
     * 封装了工具函数 infixToSuffix,用于将中缀表达式转换为后缀表达式。
     * 实现了 Iterable接口,可以迭代ExpressionElement元素对象。
     */
    
    abstract class Expression implements Iterable< ExpressionElement >
    {
    
          // ---------------------------------------------------------------------------
    
          // 使用ArrayList存储表达式元素
          protected final List< ExpressionElement > expression = new ArrayList <>() ;
    
          // 追加一个表达式元素对象,不可以追加空元素。
          public boolean append( ExpressionElement e )
          {
                if ( e == null)
                     return false ;
                expression .add ( e) ;
                return true ;
          }
    
          public boolean append( String content )
          {
                switch ( content )
                {
                case ExpressionElement . LEFT_PARENTHESES:
                     expression .add ( ExpressionDelimeter. DM_LEFT_PARENTHESES ) ;
                     break ;
                case ExpressionElement . RIGHT_PARENTHESES:
                     expression .add ( ExpressionDelimeter. DM_RIGHT_PARENTHESES ) ;
                     break ;
                case ExpressionElement . PLUS:
                     expression .add ( ExpressionOperator. OP_PLUS );
                     break ;
                case ExpressionElement . MINUS:
                     expression .add ( ExpressionOperator. OP_MINUS );
                     break ;
                case ExpressionElement . MULTIPLE:
                     expression .add ( ExpressionOperator. OP_MULTIPLE );
                     break ;
                case ExpressionElement . DIVIDE:
                     expression .add ( ExpressionOperator. OP_DEVIDE );
                     break ;
                default :
                     try
                     {
                          ExpressionOperand operand = new ExpressionOperand (content ) ; // 构造时使用了parseDouble
                          expression .add ( operand) ;
    
                     } catch (Exception e)
                     {
                          return false ;
                     }
    
                }
                return true ;
          }
    
          @Override
          public String toString()
          {
                boolean firstAdd = true ;
                StringBuilder sb = new StringBuilder () ;
                for ( ExpressionElement e : expression )
                {
                     if ( ! firstAdd)
                     {
                          sb .append ( " ") ;
                     } else
                     {
                          firstAdd = false;
                     }
                     sb .append ( e. toString ());
                }
                return sb . toString() ;
          }
    
          @Override
          public Iterator < ExpressionElement> iterator()
          {
                return expression . iterator() ;
          }
    
          public void clear()
          {
                this .expression . clear() ;
          }
    
          // 获取表达式最终的运算的结果
          public abstract double getResultValue() throws Exception ;
    
    }
    
    class SuffixExpression extends Expression
    {
    
          private double doPlus( ExpressionOperand a , ExpressionOperand b )
          {
                return a . getValue() + b .getValue () ;
          }
    
          private double doMinus( ExpressionOperand a , ExpressionOperand b )
          {
                return a . getValue() - b .getValue () ;
          }
    
          private double doMultiple( ExpressionOperand a , ExpressionOperand b )
          {
                return a . getValue() * b .getValue () ;
          }
    
          private double doDevide( ExpressionOperand a , ExpressionOperand b )
          {
                return a . getValue() / b .getValue () ;
          }
    
          // SuffixExpression 本身已经是一个后缀表达了。getResultValue计算出结果就OK了
          @Override
          public double getResultValue () throws Exception
          {
                SimpleStack <ExpressionOperand > scalc = new SimpleStack <>() ;
    
                for ( ExpressionElement e : expression )
                {
    
                     if ( e instanceof ExpressionOperand)
                     {
                          scalc .push (( ExpressionOperand) e) ;
                     } else if ( e instanceof ExpressionOperator )
                     {
    
                          ExpressionOperator operator = ( ExpressionOperator) e; // 获取这个运算符
                          ExpressionOperand opf = scalc .pop () ; // 弹出二元运算符的第二个操作数
                          ExpressionOperand ops = scalc .pop () ; // 弹出二元运算符的第一个操作数
                          ExpressionOperand temp = null ; // 存储临时运算结果
    
                          if ( opf == null || ops == null )
                                throw new Exception( "表达式不合法,不能完成计算" ) ;
    
                          if ( operator. equals (ExpressionOperator . OP_PLUS))
                          {
                                temp = new ExpressionOperand (doPlus ( ops, opf)) ;
                          } else if ( operator. equals (ExpressionOperator . OP_MINUS))
                          {
                                temp = new ExpressionOperand (doMinus ( ops, opf)) ;
                          } else if ( operator. equals (ExpressionOperator . OP_MULTIPLE))
                          {
                                temp = new ExpressionOperand (doMultiple ( ops, opf)) ;
                          } else if ( operator. equals (ExpressionOperator . OP_DEVIDE))
                          {
                                temp = new ExpressionOperand (doDevide ( ops, opf)) ;
                          }
    
                          scalc .push ( temp) ;
    
                     } // else if
    
                } // end foreach
    
                if ( scalc .size () != 1)
                     throw new Exception( "表达式不合法,不能完成计算" ) ; // 从 scalc栈中取出最后一个元素就是结果
    
                return scalc . pop() . getValue() ;
          }
    
    }
    
    class InfixExpression extends Expression
    {
          public SuffixExpression toSuffixExpression()
          {
                SuffixExpression suffix = new SuffixExpression () ; // suffix是一个用来存储表达式元素的线性表对象,对应算法中的L
                SimpleStack <ExpressionElement > sop = new SimpleStack <>() ; // sop 栈
    
                // 遍历原始表达式中的每一个元素
                for ( ExpressionElement e : expression )
                {
                     if ( e instanceof ExpressionOperand) // 如果是操作数,则直接追加到后缀表达式suffix中
                     {
                          suffix .append ( e) ;
                     } else if ( e instanceof ExpressionDelimeter ) // 如果是分界符
                     {
                          if ( e. equals (ExpressionDelimeter . DM_LEFT_PARENTHESES )) // 是 左括号,则直接压栈
                          {
                                sop .push ( e) ;
                          } else if ( e. equals (ExpressionDelimeter . DM_RIGHT_PARENTHESES )) // 是 右括号,则从 sop中弹出与这个括号配对的中间的所有元素,
                          { // 并追加到后缀表达式中
                                while ( ! sop. isEmpty () && ! sop. peek (). equals (ExpressionDelimeter . DM_LEFT_PARENTHESES ))
                                {
                                     suffix .append ( sop. pop ()); // 将元素出栈,追加到 suffix 表中去
                                }
    
                                if ( ! sop. isEmpty ())
                                {
                                     sop .pop () ; // 将栈顶的( 出栈,丢弃。
                                }
                          }
    
                     } else if ( e instanceof ExpressionOperator ) // 如果是运算符
                     {
    
                          while ( ! sop. isEmpty () && sop . peek() instanceof ExpressionOperator
                                     && 0 >= (( ExpressionOperator) e ). compareTo ((ExpressionOperator ) sop . peek()))
                          {
                                suffix .append ( sop. pop ());
                          }
                          sop .push ( e) ;
    
                     }
                } // end of foreach
    
                // 将 sop栈中剩余的元素全部追加到suffix后
                while ( ! sop. isEmpty ())
                {
                     suffix .append ( sop. pop ());
                }
    
                return suffix ;
          }
    
          @Override
          public double getResultValue () throws Exception
          {
                return toSuffixExpression () .getResultValue () ;
          }
    
    }
    
    /**
     *
     * 因为Java集合框架中的Stack类是线程安全的, 但是这里不需要这种特性,为了提高效率,使用双端队列作为内部实现,自己封装成为一个栈数据结构。
     *
     * @see java.util.Stack <E>
     * @see java.util.Deque <E>
     * @see java.util.LinkedList <E>
     */
    class SimpleStack < E>
    {
    
          private final Deque< E > deque = new LinkedList < E> ();
    
          public E pop()
          {
                return deque . pop() ; // 双端队列的第一个元素,也就是栈的栈顶
          }
    
          public E peek()
          {
                return deque . peek() ;
          }
    
          public void push( E e )
          {
                deque .push ( e) ; // 压栈
          }
    
          public int size()
          {
                return deque . size() ;
          }
    
          public boolean isEmpty()
          {
                return 0 == deque .size () ;
          }
    
          @Override
          public String toString()
          {
                StringBuilder sb = new StringBuilder () ;
                sb .append ( "栈顶[") ;
                for ( E e : deque)
                {
                     sb .append ( e. toString () + "," ) ;
                }
    
                sb .append ( "]栈底") ;
    
                return sb. toString ();
          }
    
    }
    展开全文
  • 逆波兰(后缀)表达式值C++实现

    千次阅读 2018-04-04 10:01:08
    之前的一篇文章里已经讲到里怎么将中缀表达式转化为后缀表达式:https://blog.csdn.net/weixin_39138071/article/details/79809533现在我们用C++实现如何根据后缀表达式值1、遍历后缀表达式;2、如果扫描的数字...

    之前的一篇文章里已经讲到里怎么将中缀表达式转化为后缀表达式:

    https://blog.csdn.net/weixin_39138071/article/details/79809533

    现在我们用C++实现如何根据后缀表达式求值

    1、遍历后缀表达式;
    2、如果扫描的是数字,则将其压入栈中,继续遍历;
    3、如果扫描的项目是一个二元运算符+ - * /,则栈顶到两个元素依次出栈,计算后再将结果存入栈中;(接下来到C++实现仅考虑里二元运算符)
    4、如果扫描的项目是一个一元运算符,则对栈顶元素出栈并执行该运算,然后将结果入栈;

    5、将遍历完后缀表达式以后会发现栈中其实只剩一个元素,即为结果,直接打印输出即可

    C++代码:

    #include<iostream>

    #include<stack>

    #include<string>

    using namespace std;


    int main(){

        string s;

        getline(cin,s);

        stack<int> sta;

        int left=0;

        int right=0;

        for(int i=0;i<s.size();i++){

            if(s[i]>='0'&&s[i]<='9'){

                string s2="";

                while(s[i]>='0'&&s[i]<='9'){

                    s2+=s[i];

                    i++;

                }

                sta.push(stoi(s2));

            }

            else if(s[i]!=' '){

                if(!sta.empty()){

                    right=sta.top();

                    sta.pop();

                }

                if(!sta.empty()){

                    left=sta.top();

                    sta.pop();

                }

                switch(s[i]){

                    case '+':

                        sta.push(left+right);

                        break;

                    case '-':

                        sta.push(left-right);

                        break;

                    case '*':

                        sta.push(left*right);

                        break;

                    case '/':

                        sta.push(left/right);

                        break;

                    default:

                        break;

                }

            }

        }

        cout<<sta.top()<<endl;

        return 0;

    }

    运行结果:

    9 3 1 - 3 * + 10 2 / +

    20

    Program ended with exit code: 0




    展开全文
  • 逆波兰式与卡塔兰数

    千次阅读 2010-12-02 17:00:00
    为什么不写程序自动出所有的合法逆波兰式,而非要手算? 为了讨论这两个问题,我们先来看下面的问题: 问题1(出栈序列问题):数 1 ~ n 按顺序入栈(栈后进先出的),任何时刻你可以选择让下一个数入栈,或者...

      读了我的上篇文章“一个 Lua 的凑24程序”的读者可能会产生这样的疑问:

    1. 为什么由 4 个数字和 3 个运算符组成的合法的逆波兰式就只有那 5 种?你是怎么穷举的?
    2. 为什么不写程序自动求出所有的合法逆波兰式,而非要手算?

      为了讨论这两个问题,我们先来看下面的问题:

     

    问题1(出栈序列问题):数 1 ~ n 按顺序入栈(栈是后进先出的),任何时刻你可以选择让下一个数入栈,或者让当前栈顶元素出栈(若栈非空)。求所有可能的出栈序列的个数。

    例:

    若 n = 2,有两种:

    1. 进进出出,得到出栈序列:2 1
    2. 进出进出,得到出栈序列:1 2

    若 n = 3,有五种:(下面以 1 表示进栈,-1 表示出栈)

    1. 1 -1 1 -1 1 -1,得到:1 2 3
    2. 1 -1 1 1 -1 -1,得到:1 3 2
    3. 1 1 -1 -1 1 -1,得到:2 1 3
    4. 1 1 -1 1 -1 -1,得到:2 3 1
    5. 1 1 1 -1 -1 -1,得到:3 2 1

      我们注意到:n = 3 时的出栈序列有 5 种,正好跟 4 个数字和 3 个运算符构成的逆波兰式个数相等!

     

      于是我们猜想:这两个问题是等价的

     

      为了证实这个猜想,我们把出栈序列问题改写成下面的形式:

    问题2(1,-1排列问题):将 n 个 1 和 n 个 -1 排成序列 S2n,使得对任意的 k ∈[1, 2n],满足,。求所有排列的个数。

      注意到在问题1中,若出栈入栈操作的排列顺序不同,则最后得到的数字序列也一定不同,因此出栈序列数就等于操作的排列个数,于是问题1与问题2等价

     

      回顾逆波兰式的计算过程:每当遇到一个数字,就入栈,相当于栈中元素个数 +1,而每遇到一个运算符就出栈两个数字,运算后结果入栈,相当于栈中元素个数 -1。我们还要求中间任何一步时栈中元素个数≥1。

     

      如果把入栈操作(或 1)对应于逆波兰式中的数字,出栈操作(或 -1)对应于逆波兰式中的运算符,我们立即得到:

     

      n + 1 个数字和 n 个运算符组成的合法逆波兰式的个数问题,与 n 个数的出栈序列问题等价。不同之处在于逆波兰式问题中,栈里始终有一个数字。

     

      再做进一步联想,逆波兰式相当于对表达式树做后序遍历,于是我们不禁要问:逆波兰式的个数问题与表达式树,或者说二叉树的个数问题是否等价?

    问题3(二叉树计数):求 n 个结点的二叉树的个数。

     

    例:当 n = 3 时,有 5 种:

      为了进一步讨论这个问题,我们先来看一下如何求 n 个数的出栈序列的个数 Cn

     

      为此我们将 1,-1 排列问题改写成下面的 x ≥ y 格路问题。

     

    问题4(x≥y格路问题)如图在 n * n 的方格中每次只能要么向右走,要么向上走。在 x ≥ y 的区域中,从 A 到 B 有多少种走法?

     

      将 1 与向右对应,-1 与向上对应,不难看出这两个问题的等价性。

     

      下面就来求解这个问题。

     

      设走法数为 Cn,考虑寻找 Cn 的递推公式。

     

      以下将 A 到 B 的那条斜线称为“大斜线”,斜线上的点记为 A0(= A), A1, A2, ... , An(= B)。

     

      有如下推论:从 A 到 B,且不经过 A1, A2, ... , An-1 中任何一点的走法有 Cn-1 种。

     

    证:从 A 到 B,且不经过 A1, A2, ... , An-1 中任何一点相当于从 D 走到 E 的 x≥y格路问题,故有 Cn-1 种走法。证毕。

     

      对于从 A 到 B 的任意一条路径,记这条路径中,第一次碰到大斜线的那个点为 F。则我们可以把 A 到 B 的所有路径分成如下 n 类:

     

      F = A1
      F = A2
      ...
      F = An = B

     

      注意前面 F 的定义是第一次碰到大斜线,故 F 之前的路径都没碰到。易证对于任意一条 A 到 B 的路径 L,它一定属于某一个分类,而且不可能同时属于两个不同的分类。可见这些分类是互不相交的,而且正好完全覆盖了 A 到 B 的所有路径。

     

      于是我们可以分别计算每一类的数量。

     

      对 F = Ai,显然 A 到 F 以及 F 到 B 可以看成 i 阶和 n - i 阶 x≥y格路问题,又由于 A 到 F 时没有碰大斜线,故有 Ci-1 种,而 F 到 B 有 Cn-i 种,故由乘法原理,第 i 类有:Ci-1Cn-i 种。加起来得:

     

    Cn = C0Cn-1 + C1Cn-2 + ... + Cn-1C0 ,   C0 = 1   (1)

      这样我们就得到了 Cn 的递推公式。

     

      下面再来看二叉树计数问题。设 n 个结点的二叉树有 Cn 种,除去根之后还有 n-1 个结点,给左子树分 i 个结点,则右子树有 n-1-i 个结点。显然左右子树分别化为两个低阶的二叉树计数问题。于是令 i 从 0 取到 n-1,我们得到:

    Cn = C0Cn-1 + C1Cn-2 + ... + Cn-1C0 ,   C0 = 1

      与上面的递推公式一样。故:二叉树计数问题与逆波兰式计数问题等价。

    问题5(多边形划分):将 n+2 边凸多边形划分成三角形,只能在两个顶点之间连线,每个顶点看作是不同的。有多少种划分方法?

    例:n = 3 时,五边形显然有五种划分,即从每个顶点连出两条线。

     

      这个问题与前面几个问题的等价性留给读者自证。

     

      下面我们就来求解递推关系 (1) 式。

    问题6:已知:C0 = 1,Cn = C0Cn-1 + C1Cn-2 + ... + Cn-1C0。求:Cn

    解:(母函数法)

     

      将数列 {Cn} 作为形式幂级数的系数,构造出数列 {Cn} 的母函数:

     

        f(x) = C0 + C1x + C2x2 + ... + Cnxn + ...

     

      于是:

     

        f2(x) = (C0 + C1x + C2x2 + ... + Cnxn + ...) * (C0 + C1x + C2x2 + ... + Cnxn + ...)

         = C0C0 + (C0C1 + C1C0)x + (C0C2 + C1C1 + C2C0)x2 + ...

         = C1 + C2x + C3x2 + ... + Cn+1xn + ...

     

      将上式两边同乘以 x,再加 C0(= 1),得:

     

        1 + xf2(x) = C0 + C1x + C2x2 + ... + Cn+1xn+1 + ...

         = f(x)

     

      于是我们得到关于 f(x) 的方程:

     

        1 + xf2(x) = f(x)

     

      解之,得:

     

           (2)

     

      对上式作泰勒展开(准确说是形式幂级数展开,反正就那个东西):

     

      回顾泰勒公式:

     

        

     

      令 x = -4x,a = 1/2 代入,得:

     

        

     

      其通项可化为:

     

        

        

     

      由于 Cn > 0,故可知 (2) 式中应取负号。上面的通项取负后,再除以 2x,得到 f(x) 的通项:

     

        

     

      故:

     

        

        

      这个数在组合数学中被称为卡塔兰(Catalan)数

     

      由此我们看到,从一个看似简单的逆波兰式计数问题,可以挖掘出这么多东西,其实写程序枚举所有合法的逆波兰式是可以的,相当于枚举所有满足要求的 1,-1 序列。只不过对于一个凑24程序来说太复杂,就省了。

     

      下面是我的枚举 1,-1 序列程序:

      这个程序用 C 语言编写(C 不是 C++ !),用到了部分 C99 特性,比如 bool 型,栈上的动态大小数组等,编译器用的是 GCC 4.5。所以如果你用 VC++ 可能必须改代码才能编译通过,但用 codepad(http://codepad.org/)可以编译通过并运行。codepad 的运行结果:http://codepad.org/3u8eLcar

     

      修改 main 函数中 n 的值可以输出不同的 n 的值的结果。nextSeq() 函数根据当前的序列计算下一个序列,时间复杂度 O(n)。

    展开全文
  • 中缀表达式

    千次阅读 2015-08-07 16:35:19
     中缀表达式的值问题是一个比较常见的问题之一,我们通常在编写程序时,直接写出表达式让编译器去处理,很少去关心编译器是怎么对表达式进行值的,今天我们来一起了解一下其中具体的原理和过程。  表达式...

    转自:点击打开链接 海子


    中缀表达式求值问题

      中缀表达式的求值问题是一个比较常见的问题之一,我们通常在编写程序时,直接写出表达式让编译器去处理,很少去关心编译器是怎么对表达式进行求值的,今天我们来一起了解一下其中具体的原理和过程。

      表达式一般来说有三种:前缀表达式、中缀表达式、后缀表达式,其中后缀表达式又叫做逆波兰表达式。中缀表达式是最符合人们思维方式的一种表达式,顾名思义,就是操作符在操作数的中间。而前缀表达式和后缀表达式中操作符分别在操作数的前面和操作数的后面。举个例子:

      3+2

      这个是最简单的一个中缀表达式。而其等同的前缀表达式形式为+32,后缀表达式形式为32+。

      那么一些朋友可能会问既然中缀表达式最符合人类的思维习惯,为什么还需要前缀表达式和后缀表达式?先看一个例子,假如在前面的表达式基础上加一点东西:

      3+2*5

      此时的表达式很显然,如果进行计算,则先计算2*5,最后计算加法。但是如果需要先计算加法运算呢?则必须加上括号,(3+2)*5。

      而如果用后缀表达式来表示,则为 32+5*,那么该表达式的计算顺序为3+2 —> (3+2)*5。

      区别就在这里,后缀表达式不需要用括号就能表示出 整个表达式哪部分运算先进行。同理,前缀表达式也是如此。这种表达式正好最符合计算机的处理方式,因为后缀表达式和前缀表达式求值不需要考虑优先级的问题,计算机处理起来便简单很多。

      今天我们这里主要讲解中缀表达式和后缀表达式(前缀表达式和后缀表达式很类似,就不做过多赘述),下面是讲解大纲:

    • 中缀表达式如何直接求值?
    • 后缀表达式如何直接求值?
    • 中缀表达式如何转换为后缀表达式?

    1.中缀表达式直接求值

      对于中缀表达式求值来说,一般最常见的直接解决办法就是利用栈,一个栈用来保存操作数,一个栈用来保存操作符。

      为了简便起见,暂时表达式中只考虑简单的+,-,*,/运算,只有圆括号,并且都是整数。

      假如有这样一个表达式:((3+5*2)+3)/5+6/4*2+3

      对于这样一个表达式,如果让你来设计操作数和操作符进栈的出栈的规则,你会怎么设计?

      先不看这么复杂的表达式,考虑一下简单点的,还是前面的3+2*5,那么很显然先进行乘法运算,后进行加法运算,但是由于操作符在操作数中间,所以当一个操作符进操作符栈时,该操作符的两个操作数并没有都进入到操作数栈中,那么如何解决呢?只有在后面一个操作符进操作符栈时,前面的一个操作符所作用的两个操作数才会全部进栈。比如3+2*5,栈的变化过程为:

      操作数栈:3      操作数栈:3   操作数栈:3 2 

      操作符栈:空     操作符栈:+  操作符栈:+    

      注意此时遇到操作符“*”,是不是需要弹出操作数栈中的两个操作数进行运算呢,很显然不是,因为乘法运算法比操作符栈的栈顶运算符优先级高,也就是说当前的操作符在“+”前进行运算,那么还需要将当前操作符压栈,则变成:

      操作数栈:3 2   操作数栈:3 2 5

      操作符栈:+ *  操作符栈:+ *

      此时到了表达式的结尾,既然栈顶的操作符的优先级比栈底的操作符的优先级高,那么可以取操作符栈的栈顶操作符和操作数栈的栈顶两个元素进行计算,则得到2*5=10,(注意从操作数栈先弹出的操作数为右操作数)。此时得到10 ,则应该把10继续压到操作数栈中,继续取操作符栈的栈顶操作符,依次进行下去,则当操作符栈为空时表示计算过程完毕,此时操作数栈中剩下的唯一元素便是整个表达式的值。

      再换个例子:2*5+3,这个表达式跟前面表达式的结果虽然相同,但是操作数和操作符入栈和出栈的顺序发生了很大变化:

      操作数栈:2     操作数栈:2   操作数栈:2 5  

      操作符栈:空    操作符栈:*   操作符栈:*     

       此时遇到“+”,而操作符栈的栈顶操作符为“*”,栈顶操作符优先级更高,表示此时可以取操作符栈顶操作符进行运算,那么栈变成:

      操作数栈:10   操作数栈:10 3

      操作符栈:空    操作符栈:+

      后面的过程跟前面一个例子类似。

      如果复杂一点,比如包含有括号,连续的乘除法这些怎么处理呢?道理是一样的,对于左括号直接入栈,碰到右括号,则一直将操作符退栈,直到碰到左括号,则括号中的表达式计算完毕。对于连续的乘除法,跟前面例子中处理过程类似。只需要记住一点:只有当前操作符的优先级高于操作符栈栈顶的操作符的优先级,才入栈,否则弹出操作符以及操作数进行计算直至栈顶操作符的优先级低于当前操作符,然后将当前操作符压栈。当所有的操作符处理完毕(即操作符栈为空时),操作数栈中剩下的唯一一个元素便是最终的表达式的值。而操作符的优先级为:+和-优先级是一样的,*和/优先级是一样的,+、-的优先级低于*、/的优先级。

      不过需要注意的是在求值之前需要对表达式进行预处理,去掉空格、识别 负号(区分“-”是作为减号还是负号),提取操作数等。

      对于“-”的区分,主要判别方法为:

      1)若前一个字符为‘(',则必定为负号;

      2)若前一个字符为')'或者数字,则必定为减号;

      3)若前面一个字符为其他运算符,如*,/,则必定是负号;

      3)若前面没有字符,即该字符为表达式的第一个字符,则必定是负号。

      也就是说只有一种情况下,”-“是作为减号使用的,就是前一个字符为')'或者数字的时候。

      如果判断出“-”是作为负号使用的,这里我采用“#”来代替“-”,并将其作为一种运算(优先级最高)。比如:-3*2

      我采取的做法是将"#"入栈,然后当遇到“*”时,由于栈顶操作符为"#",因此取#,然后取操作数栈的栈顶元素(只取一个)进行运算,然后再把结果压栈。






    #include <cstdio>
    #include <cstring>
    #include <stack>
    #define LL long long
    using namespace std;
    #define maxn 5005
    char s[maxn];
    
    LL num[maxn];
    char sig[maxn];
    int nn,sn;
    
    int pri(char c){
        if(c=='+'||c=='-') return 1;
        if(c=='*'||c=='/') return 2;
        if(c=='(') return 0;
    }
    
    void cal(){
        if(sig[sn]=='+') num[nn-1]=num[nn]+num[nn-1];
        if(sig[sn]=='-') num[nn-1]=num[nn-1]-num[nn];
        if(sig[sn]=='*') num[nn-1]=num[nn-1]*num[nn];
        if(sig[sn]=='/') num[nn-1]=num[nn-1]/num[nn];
        nn--;
        sn--;
    }
    
    
    LL solve(int l,int r){
        nn=sn=0;
        int curn=0;
        for(int i=l;i<=r;i++){
            if(isdigit(s[i])){
                curn=curn*10+s[i]-'0';
            }
            else {
                if(s[i]=='(') {
                    sig[++sn]=s[i];
                    continue;
                }
                if(s[i-1]!=')'){
                    num[++nn]=curn;
                    curn=0;
                }
                if(s[i]==')'){
                    while(sig[sn]!='(') cal();
                    sn--;
                    continue;
                }
                if(sn&&pri(s[i])<=pri(sig[sn])) cal();
                sig[++sn]=s[i];
            }
        }
        if(s[r]!=')') num[++nn]=curn;
        while(nn>1) cal();
        return num[1];
    }
    
    int main(){
        while(~scanf("%s",s)){
            cout<<solve(0,strlen(s)-1)<<endl;
        }
        return 0;
    }
    


    展开全文
  • 中缀表达式值问题

    2019-01-08 00:50:51
     中缀表达式的值问题是一个比较常见的问题之一,我们通常在编写程序时,直接写出表达式让编译器去处理,很少去关心编译器是怎么对表达式进行值的,今天我们来一起了解一下其中具体的原理和过程。  表达式...
  • 中序表达式

    千次阅读 2010-10-03 15:00:00
    对于一个数学表达式,语言编译系统是怎么求值的呢? 通常的做法是对一个数学中序表达式求逆波兰式(后序表达式),然后再求值。   笔者用C#写了一个中序表达式求值的类,以供参考  ...
  • 中缀、前缀和后缀表达式值问题

    千次阅读 2014-08-06 09:02:31
     中缀表达式的值问题是一个比较常见的问题之一,我们通常在编写程序时,直接写出表达式让编译器去处理,很少去关心编译器是怎么对表达式进行值的,今天我们来一起了解一下其中具体的原理和过程。  表达式...
  • 1、逆波兰表达式简介  假定给定一个只 包含 加、减、乘、除,和括号的算术表达式,你怎么编写程序计算出其结果。问题:在表达式中,括号,以及括号的多层嵌套 的使用,运算符的优先级不同等因素,使得一个算术...
  • 数据结构(2021-5-13)

    2021-05-13 17:52:24
    exit(0)什么意思 exit(0)的意思指的正常状态退出。 exit()就是退出,传入的参数程序退出时的状态码...[来看大佬怎么把算术表达式转换成逆波兰表达式并值的叭].(https://blog.csdn.net/q416983839/article/deta
  • 计算机是怎么算出来等于20的呢? 本文讲解的内容是计算机如何使用栈来表达数学中的四则运算和值。文中有两个主要的概念,分别是后缀表示法和中缀表达式如何转换成后缀表达式。 1.后缀表示法(逆波兰表示,RPN) ...
  • 中缀表达式转换为后缀表达式

    千次阅读 2018-08-14 09:22:14
    中缀表达式的值问题是一个比较常见的问题之一,我们通常在编写程序时,直接写出表达式让编译器去处理,很少去关心编译器是怎么对表达式进行值的,今天我们来一起了解一下其中具体的原理和过程。  表达式...
  • 0150. 逆波兰表达式值 0152. 乘积最大子数组 0153. 寻找旋转排序数组中的最小值 0199. 二叉树的右视图 0200. 岛屿数量 0201. 数字范围按位与 0208. 实现 Trie (前缀树) 0209. 长度最小的子数组 ...
  • 大话数据结构

    2018-12-14 16:02:18
    4.9.1后缀(逆波兰)表示法定义 104 4.9.2后缀表达式计算结果 106 4.9.3中缀表达式转后缀表达式 108 4.10队列的定义 111 电脑有时会处于疑似死机的状态。就当你失去耐心,打算了reset时。突然它像酒醒了一样,把...

空空如也

空空如也

1
收藏数 20
精华内容 8
关键字:

逆波兰是怎么求