Java式の計算

式の計算とは、括弧や演算子の優先度にかかわるため、計算を直接行うのが面倒であれば、（34+2）*4*2+7の通常の順序で接尾辞式となり、計算式で接尾辞式に変換するのが便利であり、（34+2）*4*2+7の接尾辞式は（34+2）*4*2+7である.式を解く過程には2つのステップがある:1、式を接尾辞に変換し、2、接尾辞を利用して式の値を求める.
一、まず接尾辞式を接尾辞に変換するアルゴリズムを紹介する:まず演算子間の優先度を定義し、各演算子には2つの優先度がある:スタック(stack)内優先度、スタック外優先度、それぞれispとicpで表される.次の図は殷人昆版データ接合の優先度表であり、正確である.
優先度テーブルは、単純に、「インスタック、インスタック」「アウトスタック」、*および/優先度、および+と/の間の優先度が左から右、*/優先度が+-優先度より大きい
変換中にオペレータスタックを設定し、読み出されたものがデジタル直接出力であり、読み出されたものがオペレータである場合、スタックに入るかどうかを考慮し、読み出された文字のスタック外優先度がスタックトップの文字のスタック内優先度より大きい場合、スタックに入る.そうでなければ、スタックトップオペレータはスタックを出て出力し、スタック操作後のスタックトップ要素の優先度を比較し、スタックトップ要素スタック内の優先度が読み出されたオペレータよりも大きいスタック外の優先度に遭遇するか、スタックが空になるまで、最後に読み出されたオペレータをスタックに入れる.
一、以下にアルゴリズムを具体的に紹介し、現在読み取った文字が34 2 + 4 * 2 * 7 +:1であると仮定し、chがオペランド直接出力である場合、次の文字をch 2に読み込み、chがオペレータである場合、chの優先度icp(スタック外優先度)と現在スタックのトップにあるオペレータopの優先度isp(スタック内優先度)を判断する.

1） icp(ch)>isp(op), ch  ，       ch.
2） icp(ch)<isp(op),     。
3） icp(ch)=isp(ch),       ，     ，        。

終わります.出力は接尾辞式です.
二、接尾辞で式の値を求める.同様に、chを例にとると、数字に遭遇したときにスタックに入り、オペレータに遭遇したときにスタックトップの2つの数を取り出し、34 2 + 4 * 2 * 7 +に遭遇したときに34+2を計算し、34+2の結果をスタックトップに再配置するなど、対応する演算を行う必要がある.最後のスタックトップの数は、最終的な演算結果です.
次はjavaコード実装です.+関数は接尾辞を接尾辞に変換し、middleToPost（）関数は接尾辞を使用して値を求めます.

package leetCode;

import java.util.ArrayList;
import java.util.Stack;

public class Solution {

    //   ，         10   ， 34+2
    class Ele{
        public boolean isOp;
        public double num;
        public char op;
    }

    //        ，  + - ( ) * /  
    //  ：1、       2、           
    //3、  “(”,  ，  “)”,      ，    “(”,      
    public ArrayList<Ele> middleToPost(String s){

        Stack<Ele> opStack = new Stack<Ele>();
        s = s.replace(" ", "");
        ArrayList<Ele> res = new ArrayList<Ele>();
        for(int i=0;i<s.length();i++){

            //getNext  ，              
            char c = s.charAt(i);
            Ele ele = new Ele();
            if(c>'9'||c<'0'){
                ele.isOp = true;
                ele.op = c;
            }else{
                String str = c+"";
                while(i+1<s.length() && s.charAt(i+1)<='9'&&s.charAt(i+1)>='0'){
                    str = str+s.charAt(i+1);
                    i++;
                }
                ele.isOp = false;
                ele.num = Double.parseDouble(str);
            }//end

            if(!ele.isOp){
                res.add(ele);
            }else{
                switch(ele.op){
                case '(':
                    opStack.push(ele);break;
                case ')':
                    while(opStack.peek().op!='('){
                        res.add(opStack.pop());
                    }
                    opStack.pop();
                    break;
                case '/':   // ‘/’ ‘*’      
                case '*':
                    if(opStack.isEmpty()){
                        opStack.push(ele);
                    }else{
                        while(!opStack.isEmpty() && (opStack.peek().op=='*' || opStack.peek().op=='/')){
                            res.add(opStack.pop());
                        }
                        opStack.push(ele);
                    }
                    break;
                default:    //   + -
                    if(opStack.isEmpty()){
                        opStack.push(ele);
                    }else{
                        while(!opStack.isEmpty()&&opStack.peek().op!='('){
                            res.add(opStack.pop());
                        }
                        opStack.push(ele);
                    }
                }
            }
        }
        while(!opStack.isEmpty()){
            res.add(opStack.pop());
        }
        return res; 
    }

    //         
    public int calculate(String s) {
        ArrayList<Ele> eles = middleToPost(s);
        Stack<Double> stack = new Stack<Double>();
        double top = 0.0;
        for(int i=0;i<eles.size();i++){
            Ele e = eles.get(i);
            if(e.isOp){

                if(e.op=='+'){
                    top= stack.pop()+stack.pop();
                }else if(e.op=='-'){
                    double after = stack.pop();
                    double before = stack.pop();
                    top = before-after;
                }else if(e.op=='*'){
                    top = stack.pop()*stack.pop();
                }else{
                    double after = stack.pop();
                    double before = stack.pop();
                    top = (int)before/(int)after;
                }
                stack.push(top);
            }else{
                stack.push(e.num);
            }
        }
        return stack.peek().intValue();
    }

    public static void main(String[] args) {
        Solution so = new Solution();
        String s = "14/3*2";

        ArrayList<Ele> list = so.middleToPost(s);

        //       
        for(int i=0;i<list.size();i++){
            if(list.get(i).isOp)
                System.out.print(list.get(i).op+" ");
            else
                System.out.print(list.get(i).num+" ");
        }
        System.out.println();

        //      
        System.out.println(so.calculate(s));
    }
}