Java 版 (精华区)

发信人: allen (夏夜晚风·原来的我), 信区: Java
标  题: 我的<<每日一题(2)>>解答
发信站: 哈工大紫丁香 (2002年08月14日23:40:27 星期三), 站内信件

    本来答应DW明天给答案的，运气好今天写出来了。^Q^

    算法描述：

        1. 设两个stack，一个操作数，一个操作符。

        2. 读入表达式串后，逐个扫描其中元素。遇到操作数，入操作数栈。

        3. 如果遇到操作符，则与操作符栈当前栈顶符号比较，如果优先级小于栈顶符
           号，则将其入栈；
           如果优先级大于栈顶符号，则将栈顶符号出栈，同时将操作数栈栈顶两个数
           出栈，按照刚才出栈操作符栈栈顶符号来运算，结果入操作数栈，同时将刚
           才新扫描到的操作符入栈。

        4. 如此往复，直到表达式串读完，针对操作符栈的符号进行最后运算，直到操
           作符栈遇到栈底元素#为止，操作数栈的栈顶数就是最终结果。

    运行结果：
        D:\Program\myself>java Expression
        Please Input the String:
        a+b+c*d/e
        The expression is Result=a+b+c*d/e
                          Result=5.4

    备注：
        实现了题目中的基本功能，关于“无限操作数，运算符加上(,)”的附加功能没
    有实现。而且对输入串也未作合法性检查，时间紧迫，明天再说吧，hoho


// Class Name:      Expression
// Environment:     UltraEdit 9.0 + JDK 1.4.1
// Author:          allen 8/14/02

import java.io.*;

public class Expression {

    static float[] operand=new float[6];        // 操作数栈
    static int opndPoint=1;                     // 操作数栈指针
    static char[] operator=new char[6];         // 操作符栈
    static int optrPoint=1;                     // 操作符栈指针
    static float valuePoint=0;                  // 字母变量的值
    static int strPoint=0;                      // 输入字串的指针
    static char exprElement;                    // 字串的一个字符
    static float leftOpnd,rightOpnd;            // 左操作数、右操作数
    static String inputExpr;                    // 输入表达式串

    public static void main(String args[]) throws IOException{

        operand[0]=-1; operator[0]='#';         // 初始化栈

        BufferedReader br=new BufferedReader(new
                                             InputStreamReader(System.in));
        System.out.println("Please Input the String:");
        inputExpr=br.readLine();                //读入控制台输入表达式串

        do{
            exprElement=inputExpr.charAt(strPoint++);   //读串中一个字符
            //如果是变量 则入操作数栈
            if (exprElement>='a' && exprElement<='z') pushOPND(++valuePoint);
            else {
                //是操作符，判断优先级
                switch(Precede(getTopOPTR(),exprElement)) {
                    case '<':
                        pushOPTR(exprElement);  // "<", 将操作符入栈
                        break;
                    case '>':       // ">", 将两操作数进行运算然后结果入栈
                        char optr=popOPTR();
                        pushOPTR(exprElement);
                        rightOpnd=popOPND(); leftOpnd=popOPND();
                        pushOPND(Operate(leftOpnd, optr, rightOpnd));
                        break;
                }
            }
        }while(valuePoint<5);
    
    while(getTopOPTR()!='#'){
        rightOpnd=popOPND(); leftOpnd=popOPND();
            pushOPND(Operate(leftOpnd, popOPTR(), rightOpnd));
    }

        //输出结果
        System.out.println("The expression is Result="+inputExpr);
        System.out.println("                  Result="+popOPND());
    }

    static char getTopOPTR(){               // 获取操作符栈顶符号
        return operator[optrPoint-1];
    }

    static void pushOPND(float opnd){       // 将opnd入操作数栈
        operand[opndPoint++]=opnd;
    }

    static void pushOPTR(char optr){        // 将optr入操作符栈
        operator[optrPoint++]=optr;
    }

    static float popOPND(){                 // 操作数栈顶数出栈
        float opnd;
        opnd=operand[--opndPoint];
        return opnd;
    }

    static char popOPTR(){                  // 操作符栈顶数出栈
        char optr;
        optr=operator[--optrPoint];
        return optr;
    }

    static char Precede(char optr1, char optr2){   // 判断optr1,optr2的优先级
        if (optr1=='#') return '<';
        if (optr1=='+' || optr1=='-') {
            if (optr2=='*' || optr2=='/') return '<';
            else return '>';
        }
        if (optr1=='*' || optr1=='/') return '>';
        return ' ';
    }

    static float Operate(float leftOPND, char optr, float rightOPND){
    // 进行一次运算，返回结果
        switch(optr){
            case '+':
                return leftOPND+rightOPND;
            case '-':
                return leftOPND-rightOPND;
            case '*':
                return leftOPND*rightOPND;
            case '/':
                return leftOPND/rightOPND;
        return 0;
    }
}
--
山 悠 悠
     水 悠 悠

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.25.48]
※ 修改:·allen 於 08月15日00:07:16 修改本文·[FROM: 218.7.25.48]