表达式求值的几种算法

====== 表达式求值 ======


表达式求值基本有两种算法，算法优先和语法分析


通常我们写的2+3×4叫中缀表达式，算法优先算法很依赖于和中缀表达式等价的后缀表达式，而借助二叉树求值本质也是一样的。

中缀转后缀的基本步骤

有个操作符栈opStack，保留暂时的优先级比较低的操作符，比如3+2*4，当碰到3时就要先入栈

碰到左括号(就一定进opStack，等再碰到左括号)时，将栈中直到左括号为止的所有操作符出栈使用，(使用指的是参与计算或拼二叉树，或拼后缀表达式)

碰到操作符，将栈顶开始往下的所有优先级大于等于本操作符的操作符出栈使用，本操作符入栈。

碰到操作数，直接使用。
贴一下代码先

package expression;

import java.util.Stack;

public class OperatorPrecedence
{
  /**
   * 暂不支持负号，但可以考虑，字符串开头的或操作符后紧挨的或括号后的减号必须算做负号
   * @param infixStr
   * @return
   */
    public String infix2sufix(String infixStr){
        
        StringBuilder rst = new StringBuilder();
        Stack<Operator> opStack = new Stack<Operator>();
        
        int len = infixStr.length();
        for(int i=0;i<len;i++)
        {
            char c = infixStr.charAt(i);
            //空格过滤掉
            if(c == ' ')
            {
                rst.append(" ");
            }
            else if(Character.isDigit(c) || c=='.')
            {
                rst.append(c);
            }
            else if(c == '(')
            {
                opStack.push(new Operator('('));
            }
            else if(c == ')')
            {
                while(opStack.size()>0 && !(opStack.peek().equals(new Operator('('))))
                {
                    rst.append(" "+opStack.pop().getSymbol());
                }
                //将左括号去除
                assert opStack.peek().equals(new Operator('('));
                opStack.pop();
            }
            else if(Operator.operators.contains(String.valueOf(c)))
            {
                Operator current = new Operator(c); 
                
                //栈空或当前优先级比栈顶的大才入栈,否则，栈内优先级小的挨次出栈拼结果
                //pop out all the greater percedence operator
                while(opStack.size()>0 && current.compareTo(opStack.peek())<=0)
                {
                    rst.append(" "+opStack.pop().getSymbol());
                }
                    
                //本操作符入栈
                opStack.push(current);
                rst.append(" ");
            }            
        }
        
        while(opStack.size()>0)
        {
            rst.append(" "+opStack.pop().getSymbol());
        }
        return rst.toString();
    }
    
    /**
     * @param args
     */
    public static void main(String[] args)
    {
        
        OperatorPrecedence o = new OperatorPrecedence();
        System.out.println(o.infix2sufix("4-(4-3*5+(2*4)+100)/10"));
    }

}

package expression;



import java.util.HashMap;

import java.util.LinkedList;



public class Operator implements Comparable

{

    private static HashMap<Operator,Integer> ops = new HashMap<Operator,Integer>();

    public static LinkedList<String> operators = new LinkedList<String>();

    static{

        ops.put(new Operator("("),0);

        ops.put(new Operator("+"),1);

        ops.put(new Operator("-"),1);

        ops.put(new Operator("*"),100);

        ops.put(new Operator("/"),100);        

        

        for(Operator o : ops.keySet())

        {

            operators.add(o.s);

        }

    }



    private String s;

    

    public String getSymbol()

    {

        return s;

    }

    

    @Override

    public boolean equals(Object obj)

    {

        if(!(obj instanceof Operator))

        {

            return false;

        }

        return this.s.equals(((Operator)obj).s);

    }

    

    @Override

    public int hashCode()

    {

        return this.s.hashCode();

    }

    

    public Operator(String s)

    {

        this.s = s;

    }

    public Operator(char c)

    {

        this.s = String.valueOf(c);

    }



    public int compareTo(Object o)

    {

        return ops.get(this) - ops.get(o);

    }

    

    /**

     * @param args

     */

    public static void main(String[] args)

    {

        System.out.println(ops.get(new Operator("@")));



    }



}

1.


优化：

为避免特殊处理左括号，右括号，以及最后特殊处理操作符栈中的最后剩余操作符。也将他们定义了特定的优先级。

并在栈低放了个优先级很低的特殊的操作符#,初始化一个二维表来存储优先级关系，设定只有栈中（碰到），栈中#碰到#时，优先级为相等，

这时脱去括号。
这样写出的代码更简练一些。
见严蔚敏c语言版《数据结构》，这是偶的大学教程。


2.
其中描述的允许可以拼后缀表达式，

也可以另加一个栈存放操作数，当使用操作数时入栈，当使用操作符时，靠顶两个操作数出栈运算后结果再入栈。这样就直接得到表达式的结果。

如果把其中的运算换成“构建二叉树节点”，这里可以构建出一个表达式的二叉树来（中序遍历就是中缀表达式，后序遍历就是后缀）。
这样可以构建二叉树递归计算二叉树取结果或者直接取表达式的结果
3.
表达式求值的另一种方法，也是最灵活易懂的方式利用编译原理的语法分析。
可以收工根据语法分析来，也可以使用ANTLR这个工具
手工语法分析是要有些编译原理的知识，待续。。


如果用三方工具就简单得多，见另一篇

http://appofis.iteye.com/admin/blogs/743714