王鸿百学年论文(2)

设置两个栈：存放运算符的OPTR栈和存放操作数或运算结果的OPND栈。具体算法描述如下：

（1）首先置操作数OPND栈为空栈，将#入运算符OPTR栈。

（2）依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转（3）。 （3）当前设读入的运算符为θ2，查找算符优先关系表，比较θ2与OPTR栈顶元素θ1 ：

若θ1<θ2,则θ2进OPTR栈，转（2）；

若θ1＝θ2, 如θ2为#，则分析成功，否则OPTR栈顶元素θ1出栈，并转（2）；

若θ1＞θ2，则出栈OPND栈顶元素存放到b，又出栈其新栈顶元素存放到a，再出栈OPTR栈顶元素至t，进行运算r=a t b (t为运算符)，并将结果r存入栈OPND后转（2）；

（4）若θ1和θ2之间无优先关系，则报错。 public class OperatorPriority {

private Stack optrStack; //符号栈 private Stack opndStack; //操作数栈

private String input; //键盘输入字符串 /***

* 构造函数 * @param input */

public OperatorPriority(String input) { super();

optrStack = new Stack(); opndStack = new Stack(); optrStack.push('#'); this.input = input; } /***

* 操作两个数

* @param a 操作数1 * @param b 操作数2 * @param op 操作符 * @return 运算结果 */

public float operateTwoNum(float a, float b, char op) { BigDecimal da = new BigDecimal(Float.toString(a)); BigDecimal db = new BigDecimal(Float.toString(b)); switch (op) { case '*':

return da.multiply(db).floatValue(); case '+':

return da.add(db).floatValue(); case '-':

return db.subtract(da).floatValue(); case '/': return db.divide(da,7,BigDecimal.ROUND_HALF_UP).floatValue(); //除不尽的情况取7位精确值。 case '^':

return db.pow((int)a).floatValue(); }

return 0; } /***

* 判断是否为操作符

* @param ch 被判断字符 * @return 布尔值 */

public boolean isOperator(char ch) {

if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#'||ch=='^') return true; else

return false; } /***

* 扫描字符串，判断是否对应文法，并计算出结果 * @return 计算结果

* @throws Exception 如果不符合文法，或者除数等于0，都将抛出异常 */

public String scanner() throws Exception { int postion = 0; // 字符串上指示的指针 char operator = 0; // 操作符 float a = 0, b = 0; // 操作数

String[] exp = StringUtil.splitExp(input); while (true) {

// 判断是否为运算符

if (exp[postion].length()==1&&isOperator(exp[postion].charAt(0))) { // 需要进行运算符的比较 if (!optrStack.isEmpty()) {

if (PriorityTable.getPriority(optrStack.peek().charValue(), exp[postion].charAt(0)) == '<') optrStack.push(exp[postion].charAt(0));

else if (PriorityTable.getPriority(optrStack.peek()

}

.charValue(), exp[postion].charAt(0)) == '>') { a = opndStack.pop();

b = opndStack.pop();

operator = optrStack.pop().charValue();

opndStack.push(operateTwoNum(a, b, operator)); continue;

} else if (PriorityTable.getPriority(optrStack.peek() .charValue(), exp[postion].charAt(0)) == '=') { optrStack.pop();

if (exp[postion].charAt(0) == '#') { return opndStack.pop().toString(); } } } else

optrStack.push( exp[postion].charAt(0));

}

// 为运算数时 else {

opndStack.push(Float.valueOf((exp[postion])).floatValue()); }

postion++;

if (postion >= exp.length) break;

throw new Exception(); }

三、分析归约流程图： 置初值K：=1，S[K]：=‘#’ 当前输入符读入a S[K] ∈VT J:J :N N J:=k J:=k-1 J:=k J:=k-1 S[j]>a S[j]>a Y Y Q:= S[j] N N S[K]

图1-1

四、运行

从键盘输入表达式串，利用算符优先法求出其值，如输入表达式有错，则给出报错提示。表达式以“#”结尾。 从键盘输入句子： package com.op.util;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class IOUtil { /***

* 得到从键盘输入的字符串 * @return 字符串 */

public static String getStringFromKeyBoard() { try {

BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

System.out.print(\请输入一个表达式以#号结束：\ String str=reader.readLine(); //获取字符串 // System.out.println(\您输入的字符串是：\ return str;

} catch (IOException e) {

e.printStackTrace(); }

return null; } }

五、测试