编程论坛 » 数据结构与算法 » 谁知道怎样用堆栈把中缀表达式转为后缀表达式

jy00873757 发表于 2008-2-13 12:36

谁知道怎样用堆栈把中缀表达式转为后缀表达式

[em02] [em02] [em02] [em02]

roy_guo 发表于 2008-2-13 19:56

一年前写的，主要看看核心算法吧。。。细节可能会有点问题
// 1. 将读到的数字依次放入数字栈
// 2. 读出的符号的优先级若不大于符号栈顶元素的优先级，则将栈顶元素弹出参与运算。
// 3. 括号起隔离作用
// 4. 优先级 '#' < +,- < *,/

public class ExpressionCalculation
{
        private String InfixationExpression;
        private myStack1 EStack;
       
        public ExpressionCalculation()
        {
                this("1*2+(3-5/4)*6");       
        }
       
        public ExpressionCalculation( String expression )
        {
                // 表达式后加自定义结束符'#'
                InfixationExpression = expression+'#';
                EStack = new myStack1();
                System.out.print(expression);       
        }
       
        public void ChangeToSuffixExpression()
        {        
                myStack TStack = new myStack();       
                TStack.push("#");
               
                int i = 0;
                String number = "";
                while( i < InfixationExpression.length() )
                {
                        if( (InfixationExpression.charAt(i) > 47) && (InfixationExpression.charAt(i) < 58) )
                        {
                                number += InfixationExpression.charAt(i);       
                        }
                        else
                        {
                                if(number != "")
                                {
                                        EStack.push(Integer.parseInt(number));
                                        number = "";
                                }
                                // 如果符号为+，-,若栈中符号优先级高，则将栈中取出运算
                                if( (InfixationExpression.charAt(i) == '+') || (InfixationExpression.charAt(i) == '-') )
                                {
                                        while( (TStack.top() != "#") && (TStack.top() != "(") )
                                        {
                                                String t = TStack.top();
                                                Calculate(t);
                                                TStack.pop();
                                        }
                                        TStack.push(InfixationExpression.charAt(i)+"");
                                }
                                //遇结束符，则将符号栈中符号全部取出运算
                                else if(InfixationExpression.charAt(i) == '#')
                                {
                                        while(TStack.getLength() > 0)
                                        {
                                                String t = TStack.top();
                                                Calculate(t);
                                                TStack.pop();       
                                        }       
                                }
                               
                                else if( (InfixationExpression.charAt(i) == '*') || (InfixationExpression.charAt(i) == '/') )
                                {
                                        while( (TStack.top() == "*") || (TStack.top() == "/") )
                                        {
                                                String t = TStack.top();
                                                Calculate(t);
                                                TStack.pop();
                                        }
                                        TStack.push(InfixationExpression.charAt(i)+"");
                                }
                                else if(InfixationExpression.charAt(i) == '(')
                                {
                                        TStack.push("(");       
                                }
                                else if(InfixationExpression.charAt(i) == ')')
                                {
                                        while(!TStack.top().equals("("))
                                        {
                                                String t = TStack.top();
                                                Calculate(t);
                                                TStack.pop();
                                        }
                                        TStack.pop();       
                                }
                        }
                        i ++;
                }
        }
       
        private void Calculate( String op )
        {
                if( op.equals("#") )
                {
                        int result = EStack.top();
                        System.out.println(" = " + result);
                }
                else
                {
                        int num2 = EStack.top();
                        EStack.pop();
                        int num1 = EStack.top();
                        EStack.pop();

                        if(op.equals("+"))
                        {
                                EStack.push( num1+num2 );
                        }
                        else if(op.equals("-"))
                        {
                                EStack.push( num1-num2 );       
                        }
                        else if(op.equals("*"))
                        {
                                EStack.push( num1*num2 );       
                        }
                        else if(op.equals("/"))
                        {
                                EStack.push( num1/num2 );       
                        }
                        else
                        {
                                System.out.println("Error!");       
                        }                       
                }       
        }
       
        public static void main(String args[])
        {
                ExpressionCalculation ec = new ExpressionCalculation();
                ec.ChangeToSuffixExpression();       
        }
}

jy00873757 发表于 2008-2-14 11:32

不需要运算,转换就OK了,我想知道多一些算法

[em02] [em02] [em02] [em02]

jy00873757 发表于 2008-2-14 11:32

代码不用了,说说思路就OK

[em01] [em01] [em01] [em01]

jy00873757 发表于 2008-2-14 11:38

算法越多越好

谢谢各位了

查看完整版本: 谁知道怎样用堆栈把中缀表达式转为后缀表达式