月度归档： 2016 年 5 月

import java.util.Stack;


public class RPN
{
    public Long Cal(String s){
        Stack a = this.Expression2Stack(s);
        Stack rpnstack = this.Turn2RPN(a);
        return this.Eval(rpnstack);
    }
    public Long Eval(Stack rpnStack){
        Stack<Long> num = new Stack();
        for(Object o:rpnStack){
            if(o instanceof Operate) 
            {
                Operate tmp = (Operate)o;
                Long num1 = num.pop();
                Long num2 = num.pop();
                switch (tmp){
                    case PLUS:{
                        num.push(num2+num1);
                        break;
                    }
                    case MINUS:{
                        num.push(num2-num1);
                        break;
                    }
                    case MUTIPLE:{
                        num.push(num1*num2);
                        break;
                    }
                    case DIVIE:{
                        num.push(num2/num1);
                        break;
                    }
                    case POWERDE:{
                        num.push((long)(Math.pow(num2.doubleValue(),num1.doubleValue())));
                        break;
                    }
                }
            }
            else{
                String tmp = (String) o;
                if(this.isNumberic(tmp))
                    num.push(Long.valueOf((String)o));
            }
        }
        return num.pop();
    }
    private boolean isNumberic(String s){
        for(char c:s.toCharArray()){
            if(!Character.isDigit(c))return false;
        }
        return true;
    }
    private Stack Turn2RPN(Stack Expression)
    {
        Stack s1 = new Stack();
        s1.push(Operate.NONE);
        Stack s2 = new Stack();
        for (Object x : Expression)
        {
            if (x instanceof Operate)
            {
                if (x == Operate.LEFTPARENTHESE)
                {
                    s1.push(x);
                }
                else if (x == (Operate.RIGHTPARENTHESE))
                {
                    while (true)
                    {
                        if (s1.lastElement() == Operate.LEFTPARENTHESE)
                        {
                            s1.pop();
                            break;
                        }
                        else
                        {
                            s2.push(s1.pop());
                            
                        }
                    }
                }
                else if (x instanceof Operate && s1.lastElement().equals(Operate.LEFTPARENTHESE))
                {
                    s1.push(x);
                }
                else if (x instanceof Operate && !s1.lastElement().equals(Operate.LEFTPARENTHESE))
                {
                    if (((Operate)s1.lastElement()).getPiority() < ((Operate)x).getPiority())
                    {
                        s1.push(x);
                    }
                    else
                    {

                        while (true)
                        {
                            if (((Operate)s1.lastElement()).getPiority() < ((Operate)x).getPiority())
                            {
                                break;
                            }
                            if (s1.lastElement().equals(Operate.LEFTPARENTHESE))
                            {
                                break;
                            }
                            s2.push(s1.pop());
                        }
                        s1.push(x);
                    }
                }
            }
            else
            {
                s2.push(x);
            }
        }
        while (!s1.empty())
        {
            s2.push(s1.pop());
        }
        s2.pop();
        return s2;
    }

    private Stack Expression2Stack(String Expression)
    {
        Stack expression = new Stack();
        StringBuffer numString = new StringBuffer();
        for (char charater : Expression.toCharArray())
        {

            switch (charater)
            {
                case '+':
                {
                    if (numString.length() != 0)
                        expression.push(numString.toString());
                    numString = new StringBuffer();
                    expression.push(Operate.PLUS);

                    break;
                }
                case '-':
                {
                    if (numString.length() != 0)
                        expression.push(numString.toString());
                    numString = new StringBuffer();
                    expression.push(Operate.MINUS);
                    break;
                }
                case '*':
                {
                    if (numString.length() != 0)
                        expression.push(numString.toString());
                    numString = new StringBuffer();
                    expression.push(Operate.MUTIPLE);
                    break;
                }
                case '/':
                {
                    if (numString.length() != 0)
                        expression.push(numString.toString());
                    numString = new StringBuffer();
                    expression.push(Operate.DIVIE);
                    break;
                }
                case '^':{
                    if (numString.length() != 0)
                        expression.push(numString.toString());
                    numString = new StringBuffer();
                    expression.push(Operate.POWERDE);
                    break;
                }
                case '(':
                {
                    if (numString.length() != 0)
                        expression.push(numString.toString());
                    numString = new StringBuffer();
                    expression.push(Operate.LEFTPARENTHESE);
                    break;
                }
                case ')':
                {
                    if (numString.length() != 0)
                        expression.push(numString.toString());
                    numString = new StringBuffer();
                    expression.push(Operate.RIGHTPARENTHESE);
                    break;
                }
                default:
                {
                    numString.append(charater);
                }
            }
        }
        if(numString.length()>0)expression.push(numString.toString());
        return expression;
    }
}

enum Operate
{
    NONE("#", 0),
    PLUS("PLUS", 1),
    MINUS("MINUS", 1),
    MUTIPLE("MUTIPLE", 2),
    DIVIE("DIVIE", 2),
    POWERDE("POWDE",3),
    LEFTPARENTHESE("LEFTPARENTHESE", 4),
    RIGHTPARENTHESE("RIGHTPARENTHESE", 4);

    private int piority;

    private String operate;

    Operate(String operate, int i)
    {
        this.piority = i;
        this.operate = operate;
    }

    public int getPiority()
    {
        return piority;
    }
}