Java中缀表达式转后缀表达式并计算

表达式一般有前缀表达式、中缀表达式和后缀表达式3种表现形式。其中，中缀表达式是平时手写算术表达式的一种描述形式，将运算符放在两个操作数中间，按人的思维来运算。但由于运算符有优先级，计算机无法像人一样思考，只能死板执行，所以计算时用中缀表达式很不方便。而后缀表达式（逆波兰表达式）区别于中缀表达式，是将运算符放在两个操作数之后，无运算符优先和无括号约束问题，很适合计算机进行计算。

因此，我们常常需要将中缀表达式转为后缀表达式再进行计算。

中缀表达式转后缀表达式步骤：

• 初始化一个运算符栈
• 左到右依次读取中缀表达式字符串的每一个字符
• 如果是左括号，直接入栈
  
• 如果是操作数，送到后缀表达式
  
• 如果是运算符，则：

1.   若栈为空，入栈
2.   若栈非空。如果运算符优先级高于栈顶运算符，入栈；否则，反复弹出栈顶优先级低的运算符送到后缀表达式，最后将当前运算符入栈。

• 如果是右括号，反复将栈顶运算符弹出送到后缀表达式直到遇左括号，弹出左括号
• 重复以上步骤直到字符读取完毕。若运算符栈非空，则将栈中剩余所有运算符送到后缀表达式中

示例：  中缀表达式 (2+3)*(6-4)/5

后缀表达式的计算：

• 初始化一个操作数栈
• 从左到右读取后缀表达式中的字符

1.     若当前字符为操作数，入栈
2.     若当前字符为运算符，则从栈顶弹出两个操作数分别作为第2个操作数和第一个操作数，进行运算，将结果入栈

• 重复以上步骤直到字符读取完毕。操作数栈中的栈顶元素即为最终结果。

完整代码如下：

public class Calculate {

    //将中缀表达式转为后缀表达式
    public String infixToPostfix(String infix)
    {
        Stack stack=new Stack();
        String postfix=new String();
        for(int i=0; infix!=null && i<infix.length(); i++)
        {
            char c=infix.charAt(i);
            //判断c不为空格
            if(c!=' ')
            {
                //若c为左括号,压栈
                if(c=='(')
                {
                    stack.push(c);
                }
                //若c为右括号,弹出栈顶元素直到左括号
                else if(c==')')
                {
                    char top=(char)stack.pop(); //弹出栈顶元素
                    while(top!='(')
                    {
                        postfix=postfix.concat(String.valueOf(top));
                        top=(char)stack.pop();
                    }
                }
                //若c为运算符
                else if(isOperator(c))
                {
                    if(!stack.isEmpty())    //栈非空
                    {
                        char top=(char)stack.pop();    //每次取出栈顶
                        if(getPriority(c)>getPriority(top))    //若运算符优先级大于栈顶优先级，则压回栈
                            stack.push(top);
                        else    //若运算符优先级小于等于栈顶优先级，不断取出栈中运算符
                        {
                            while (getPriority(c) <= getPriority(top)) {
                                postfix = postfix.concat(String.valueOf(top));
                                if (stack.isEmpty())
                                    break;
                                top = (char) stack.pop();
                            }
                        }
                    }
                    stack.push(c);
                }
                //若c为操作数
                else
                {
                    postfix=postfix.concat(String.valueOf(c));
                }
            }
        }
        while(!stack.isEmpty())
        {
            postfix=postfix.concat(String.valueOf(stack.pop()));
        }
        return postfix;
    }

    //判断字符是否为运算符
    public boolean isOperator(char c)
    {
        if(c=='+' || c=='-' || c=='*' || c=='/' || c=='%' || c=='^')
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    //返回运算符的优先级
    public int getPriority(char c)
    {
        if(c=='+' || c=='-')
            return 1;
        else if(c=='*' || c=='/' || c=='%')
            return 2;
        else if(c=='^')
            return 3;
        else
            return 0;
    }

    //对后缀表达式求值
    public double numberCalculate(String result)
    {
        Stack stack=new Stack();
        for(int i=0; result!=null && i<result.length(); i++)
        {
            char c=(char)result.charAt(i);
            //如果是操作数，则弹出栈顶两个数运算，将结果压栈
            if(isOperator(c))
            {
                double d2=Double.valueOf(stack.pop().toString());
                double d1=Double.valueOf(stack.pop().toString());
                double d3=0;

                if(c=='+')
                {
                    d3=d1+d2;
                }
                else if(c=='-')
                {
                    d3=d1-d2;
                }
                else if(c=='*')
                {
                    d3=d1*d2;
                }
                else if(c=='/')
                {
                    d3=d1/d2;
                }
                else if(c=='%')
                {
                    d3=d1%d2;
                }
                else if(c=='^')
                {
                    d3=Math.pow(d1,d2);
                }
                stack.push(d3);
            }
            else
            {
                stack.push(c);
            }
        }
        return (Double)stack.pop();
    }

    public static void main(String[] args)
    {
        Calculate calculate=new Calculate();
        String infix= "(2+3)*(6-4)/5";
        String postfix = calculate.infixToPostfix(infix);
        double result=calculate.numberCalculate(postfix);
        System.out.println("中缀转后缀结果： "+postfix);
        System.out.println("后缀表达式计算结果： "+result);
    }
}

    运行结果：

注意：以上适用于含有二元运算符且操作数是一位整数的中缀表达式，如有特别要求可根据实际情况对代码进行拓展。代码容易读懂，

重要的是掌握方法。（凡星逝水2017）