编译原理 - 算符优先分析方法（JAVA）

1. 理论依据

1）判断输入文法是否算符文法
根据定义：产生式右部不包含两个相邻非终结符的文法称为算符文法。
我们们对输入的文法进行依次遍历，查看每个产生式的右部进行遍历查找，如果发现出现两个非终极符连续出现，则发出提示，文法不符，并要求重新输入文法。

2）采用由定义构造算符优先关系集合并构造矩阵

由以上公式，先得到对应的FIRSTVT与LASTVT集合，再依次遍历文法找到所需的…aV…或者…Vb…产生式，与FIRSTVT（V）或者LASTVT（V）卡氏积，得到>,<,=的算符优先关系，将这些关系存入算法关系集合，之后将得到的算法优先关系集合解析，构造出算符优先关系矩阵。打印出来。
同时对于起始S和结束符#,有#<FIRST(S),LASTVT(S)>#,且对#S#,有#=#。
即在优先关系矩阵右边和下边构建添加#符号，方便初始情况等一些特殊情况的处理。

3）算符优先分析算法分析句子

算符优先分析算法是自下而上的语法分析方法，是对当前句型不断查找最左素短语进行规约的过程。寻找最左短语时，先找到最左素短语的末尾终结符，然后再向前搜索最左素短语的首终结符。
代码使用的流程为：使用符号栈的栈顶非终结字符a与输入流首字符b构成（a,b）到算符优先矩阵里查找优先关系，判断当前是否是=，或者<,如果是，则继续从输入流首字符输入到符号栈，如果是>,则进行规约动作；并将规约的终结符入栈。
直到输入流为“#”，此时再来判断符号栈栈顶符号是否为文法的输入符号。
完成对该句子的文法合法性分析。

3.数据结构分析

（1）FIRSTVT集合与LASTVT集合
由以上分析我们可以得出，FIRSTVT与LASTVT集合都是基于（终结符）->{非终结符集合}的key->value形式。
故采用以下形式：
private static Map<Character, Set> firstVt = new HashMap<>();
private static Map<Character, Set> lastVt = new HashMap<>();
其中，<Character，Set> 第一个Character为终结符，Set为该终结符求出的非终结符集合。
（2）算符矩阵集合
用Map<String,Character>存,String中存优先变的行值和列值,Character表示String中所存行列的大小关系如"ab"表示行为’a’,列为’b’的时候,关系为Character中的值。
即（a，b）a与b拼接存入String，Character存入（a,b）对应的关系“<” ,“>”,或者“=”。例子：ab 对应 =。
同时代码多增加了一列一行“#”，以来处理初始情况和结束情况。

（3）句子分析
句子分析采用了栈结构，将“#”符号放入符号栈底。同时要求输入句子时以“#”结尾；

伪代码如下：

k:=1; 
S[k]:= ‘#’;
REPEAT把下一个输入符号读进 a 中； IF S[k] ∈ Vt THEN j:=k ELSE j:= k-1;WHILE S[j] > a DO BEGINREPEATQ:=S[j]; IF S[j-1]∈ VT THEN j:j-1 ELSE j:j-2UNTIL S[j] < Q;把 S[j+1]…S[k]归约为某个 N；k:=j+1;S[k]:=N;END OF WHILE;IF S[j] < a OR s[j] = a THENBEGIN k:=k+1;S[k]:=N; ENDELSE ERROR
UNTIL  a = ‘#’ 

2. 结果截图

3. 实现代码

package parser.simplepriority;import java.util.*;public class analyze {/*** FIRSTVT集合*/private static Map<Character, Set<Character>> firstVt = new HashMap<>();/*** LASTVT集合*/private static Map<Character, Set<Character>> lastVt = new HashMap<>();/*** 输入的文法*/private static List<String> input = new ArrayList<>();/*** 终结符*/private static Set<Character> End = new LinkedHashSet<>();/*** 非终结符*/private static Set<Character> NoEnd = new LinkedHashSet<>();/*** 算符矩阵*/private static Map<String, Character> matrix = new HashMap<>();private static Scanner in = new Scanner(System.in);/*** 文法的左右分割一一对应*/private static Map<Character, List<String>> produce = new HashMap<>();/*** 获得firstVt集合*/private static void getFirstVT(Character s, Set<Character> fvt) {String str = null;int i = 0;for (i = 0; i < input.size(); i++) {if (input.get(i).charAt(0) == s) {str = input.get(i);}}for (i = 3; i < str.length(); i++) {if (str.charAt(i) < 65 || str.charAt(i) > 90) {//P->a.....，即以终结符开头，该终结符入Firstvtif ((str.charAt(i - 1) == '>' && str.charAt(i - 2) == '-') || str.charAt(i - 1) == '|') {fvt.add(str.charAt(i));}//P->Qa....，即先以非终结符开头，紧跟终结符，则终结符入Firstvtif ((str.charAt(i - 2) == '|' || (str.charAt(i - 2) == '>' && str.charAt(i - 3) == '-')) && str.charAt(i - 1) >= 65 && str.charAt(i - 1) <= 90) {fvt.add(str.charAt(i));}}//若有P->Q.....，即以非终结符开头，该非终结符的Firstvt加入P的Firstvtif (str.charAt(i - 1) == '|' && str.charAt(i) >= 65 && str.charAt(i) <= 90) {if (str.charAt(i) == str.charAt(0)) {continue;}//递归getFirstVT(str.charAt(i), fvt);}}}/*** 获得lastVt集合*/private static void getLastVT(Character s, Set<Character> lvt) {String str = null;int i = 0;for (i = 0; i < input.size(); i++) {if (input.get(i).charAt(0) == s) {str = input.get(i);}}for (i = 3; i < str.length(); i++) {if (str.charAt(i) < 65 || str.charAt(i) > 90) {//P->....aQ，即先以非终结符结尾，前面是终结符，则终结符入Lastvt,Q处于产生式最后一位的情况if (i == str.length() - 1 || (i == str.length() - 2 && str.charAt(i + 1) >= 65 && str.charAt(i + 1) <= 90 && str.charAt(i) != '|' && (str.charAt(i) != '>' && str.charAt(i) != '-'))) {lvt.add(str.charAt(i));}if (i < str.length() - 2) {//P->....aQ，即先以非终结符结尾，前面是终结符，则终结符入Lastvtif (str.charAt(i + 1) == '|' || (str.charAt(i + 2) == '|' && str.charAt(i + 1) >= 65 && str.charAt(i + 1) <= 90)) {lvt.add(str.charAt(i));}}} else {//P->....Q，即以非终结符结尾，该非终结符的Lastvt入P的Lastvtif (i == str.length() - 1) {if (str.charAt(i) == str.charAt(0)) {continue;}getLastVT(str.charAt(i), lvt);} else if (str.charAt(i + 1) == '|') {if (str.charAt(i) == str.charAt(0)) {continue;}//P->....Q，即以非终结符结尾，该非终结符的Lastvt入P的LastvtgetLastVT(str.charAt(i), lvt);}}}}/*** 显示firstVt集合和lastVt集合*/private static void DisplayFirstVT_LastVT() {for (int i = 0; i < input.size(); i++) {Set<Character> fvt = new HashSet<>();getFirstVT(input.get(i).charAt(0), fvt);firstVt.put(input.get(i).charAt(0), fvt);}for (int i = 0; i < input.size(); i++) {Set<Character> lvt = new HashSet<>();getLastVT(input.get(i).charAt(0), lvt);lastVt.put(input.get(i).charAt(0), lvt);}System.out.println("firstVt集合如下:");for (Map.Entry<Character, Set<Character>> entry : firstVt.entrySet()) {System.out.print("firstVt(" + entry.getKey() + "): {");int flag = 0;for (Character value : entry.getValue()) {flag++;System.out.print(value);if (flag != entry.getValue().size()) {System.out.print(",");}}System.out.println("}");}System.out.println("lastVt集合如下:");for (Map.Entry<Character, Set<Character>> entry : lastVt.entrySet()) {System.out.print("lastVt(" + entry.getKey() + "): {");int flag = 0;for (Character value : entry.getValue()) {flag++;System.out.print(value);if (flag != entry.getValue().size()) {System.out.print(",");}}System.out.println("}");}}/*** 获取所有终结符*/private static void getEnd() {for (int i = 0; i < input.size(); i++) {String temp = input.get(i);for (int j = 3; j < temp.length(); j++) {if (temp.charAt(j) < 65 || temp.charAt(j) > 90 && temp.charAt(j) != '|') {End.add(temp.charAt(j));}}}End.add('#');}/*** 获取所有非终结符*/private static void getNoEnd() {for (int i = 0; i < input.size(); i++) {String temp = input.get(i);for (int j = 3; j < temp.length(); j++) {if (temp.charAt(j) >= 65 && temp.charAt(j) <= 90) {NoEnd.add(temp.charAt(j));}}}}/*** 将每一行的文法分离,如E->E+T|T分离成E和E+T,T*/private static void getProduce() {for (int i = 0; i < input.size(); i++) {List<String> list = new ArrayList<>();String str = input.get(i);StringBuffer a = new StringBuffer();for (int j = 3; j < str.length(); j++) {if (str.charAt(j) != '|') {a.append(str.charAt(j));} else {list.add(a.toString());//清空aa.delete(0, a.length());}}list.add(a.toString());produce.put(str.charAt(0), list);}}/*** 错误*/public static void partError() {matrix.put(")(", 'b');matrix.put("((", 'b');matrix.put("(#", 'a');}/*** 构造算符优先矩阵并打印* 用Map<String,Character>存,String中存优先变得行值和列值,* Character表示String中所存行列的大小关系如"++"表示行为'+',列为'+'的时候,关系为Character中的值** @return*/private static void priorityMatrix() {for (int i = 0; i < input.size(); i++) {String str = input.get(i);for (int j = 3; j < input.get(i).length(); j++) {if ((str.charAt(j) < 65 || str.charAt(j) > 90) && (str.charAt(j) != '|')) {if (j < str.length() - 1 && (str.charAt(j + 1) < 65 || str.charAt(j + 1) > 90)) {String temp = str.charAt(j) + "" + str.charAt(j + 1);matrix.put(temp, '=');} else {if (j < str.length() - 2 && (str.charAt(j + 2) < 65 || str.charAt(j + 2) > 90) && (str.charAt(j + 2) != '|')) {matrix.put(str.charAt(j) + "" + str.charAt(j + 2), '=');}}if (j < str.length() - 1 && str.charAt(j + 1) >= 65 && str.charAt(j + 1) <= 90) {Set<Character> coll = firstVt.get(str.charAt(j + 1));for (Character value : coll) {matrix.put(str.charAt(j) + "" + value, '<');}}if (j - 1 != 2 && str.charAt(j - 1) >= 65 && str.charAt(j - 1) <= 90) {Set<Character> coll = lastVt.get(str.charAt(j - 1));for (Character value : coll) {matrix.put(value + "" + str.charAt(j), '>');}}}}}Set<Character> coll = firstVt.get(input.get(0).charAt(0));for (Character value : coll) {matrix.put('#' + "" + value, '<');}Set<Character> coll1 = lastVt.get(input.get(0).charAt(0));for (Character value : coll1) {matrix.put(value + "" + '#', '>');}partError();for (Character value : End) {for (Character value1 : End) {if (matrix.get(value + "" + value1) == null) {matrix.put(value + "" + value1, 'b');}}}matrix.put("##", '=');/*        for (Map.Entry<String, Character> entry : matrix.entrySet()) {System.out.println(entry.getKey()+"   "+entry.getValue());}*/getEnd();System.out.println("\n构造的算符优先关系表如下:");int kong = 0;for (Character value : End) {if (kong == 0) {System.out.print("   ");}kong++;System.out.print(value);if (kong != End.size()) {System.out.print("  ");}}System.out.println();for (Character value : End) {System.out.print(value);for (Character value1 : End) {Character ch = matrix.get(value + "" + value1);if (ch != null) {System.out.print("  " + ch);} else {System.out.print("  " + " ");}}System.out.println();}}/*** 判断其是不是算符文法* 如果没有连个连续非终结符号相连的就是算符优先文法* @return*/private static boolean isOperator() {int i;for (i = 0; i < input.size(); i++) {for (int j = 0; j < input.get(i).length() - 1; j++) {String str = input.get(i);if (str.charAt(j) >= 65 && str.charAt(j) <= 90) {if ((str.charAt(j + 1) >= 65 && str.charAt(j + 1) <= 90)) {return false;}}}}return true;}/*** 判断其是不是终结符* @return*/private static boolean isEnd(Character ch) {for (Character value : End) {if (value.equals(ch)) {return true;}}return false;}/*** 判断其是不是非终结符* @return*/private static boolean isNoEnd(Character ch) {for (Character value : NoEnd) {if (value.equals(ch)) {return true;}}return false;}/*** 根据产生式右部分返回左边* @return*/private static char retLeft(String str) {char ch = 0;for (Map.Entry<Character, List<String>> map : produce.entrySet()) {ch = map.getKey();for (String value : map.getValue()) {if (value.length() != str.length()) {continue;}int i;for (i = 0; i < str.length(); i++) {if (str.charAt(i) >= 65 && str.charAt(i) <= 90) {if (value.charAt(i) >= 65 && value.charAt(i) <= 90) {} else {break;}} else {if (value.charAt(i) != str.charAt(i)) {break;}}}if (i == str.length()) {return ch;}}}return 0;}/*** 将字符数组转换成字符串* @param list* @return*/public static String replaceToString(List<Character> list) {StringBuffer a = new StringBuffer();for (Character value : list) {if (value != ',' && value != '[' && value != ']') {a.append(value);}}return a.toString();}/*** 算符优先分析过程* 使用一个符号栈，用它寄存终结符和非终结符,k代表符号栈的深度* 在正常情况下，算法工作完毕时，符号栈S应呈现:#N*/public static void analysisProcess() {int status = 0;int count = 0;int k = 0;int j = 0;int step = 0;String gui = null;System.out.println("请输入要分析的句子(注意:记得以'#'结束)");String sentence = null;sentence = in.nextLine();if (sentence.charAt(sentence.length() - 1) != '#') {sentence = sentence + "#";}List<Character> listStack = new ArrayList<>();System.out.printf("%-8s%-20s%-8s%-10s%-8s\n", "步骤", "栈", "a读入", "剩余串", "操作");listStack.add('#');char a = sentence.charAt(step++);do {if (status == 0) {if (count != 0) {System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", "移进", count, replaceToString(listStack), a, sentence.substring(step));} else {System.out.printf("%-8d %-20s %-8c %-10s", count, replaceToString(listStack), a, sentence.substring(step));}} else {System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", gui, count, replaceToString(listStack), a, sentence.substring(step));}char ch = listStack.get(k);if (isEnd(ch)) {j = k;} else if (j >= 1) {j = k - 1;}char temp = 0;if (matrix.get(listStack.get(j) + "" + a) != null) {//规约while (matrix.get(listStack.get(j) + "" + a).equals('>')) {if (listStack.size() == 2 && a == '#') {break;}StringBuffer judge = new StringBuffer();do {temp = listStack.get(j);if (isEnd(listStack.get(j - 1))) {j = j - 1;} else {j = j - 2;}} while (!matrix.get(listStack.get(j) + "" + temp).equals('<'));for (int i = j + 1; i < listStack.size(); i++) {judge.append(listStack.get(i));}int te = listStack.size();for (int t = j + 1; t < te; t++) {listStack.remove(j + 1);}char res = retLeft(judge.toString());if (res != 0) {count++;k = j + 1;listStack.add(res);status = 1;gui = "用" + res + "->" + judge.toString() + "规约";if (status == 0) {System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", "移进", count, replaceToString(listStack), a, sentence.substring(step));} else {System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", gui, count, replaceToString(listStack), a, sentence.substring(step));}}}}//移进if (matrix.get(listStack.get(j) + "" + a).equals('<') || matrix.get(listStack.get(j) + "" + a).equals('=')) {count++;k++;status = 0;listStack.add(a);} else {switch (matrix.get(listStack.get(j) + "" + a)) {case 'a':System.out.print("非法左括号! ");return;case 'b':System.out.print("缺少运算符! ");return;case 'c':System.out.print("缺少表达式! ");return;default:break;}}if (listStack.size() == 2 && a == '#') {break;}if (step < sentence.length()) {a = sentence.charAt(step++);} else {break;}} while (listStack.size() != 2 || a != '#');System.out.printf("%-8s\n", "分析成功");}/*** 主函数** @param args*/public static void main(String[] args) {int flag = 1;String a;System.out.println("请输入文法:");while (flag != 0) {while (!(a = in.nextLine()).equals("")) {input.add(a);}if (isOperator()) {System.out.println("此文法是算符文法!");flag = 0;} else {System.out.println("此文法不是算符文法!请重新输入:");input.clear();}}getEnd();getNoEnd();getProduce();DisplayFirstVT_LastVT();priorityMatrix();analysisProcess();}
}

package parser.simplepriority;import java.io.File;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;public class OperatorPriorityAnalyst {final String INPUT_PATH = "src/Test/input.txt";//final String OUTPUT_PATH = "src/Test/output.txt";final String VT = "i+-*/()#";final int EXPRESSION_ACCEPT = 0;final int EXPRESSION_WRONG = 1;final int SHIFT = -1;               //移进final int REDUCE = 1;               //规约final int EQUAL = 0;HashMap<String, Integer> table;HashMap<Character, Integer> operatorPriorityTable;HashMap<String, String> reduceTable;                //栈顶规约表String sequence;boolean meetZero = false;           //计算过程中是否出现0做除数public void analysis() throws Exception {int turn = 1;init();Scanner scanner = new Scanner(new File(INPUT_PATH));//FileWriter writer = new FileWriter(new File((OUTPUT_PATH)));String oriExpression;//original expressionwhile (scanner.hasNextLine()) {StringBuffer outputBuffer = new StringBuffer();//output.txt information for each input.txt lineoriExpression = scanner.nextLine();oriExpression = oriExpression.substring(0, oriExpression.length() - 1);//gets rid of the ;String[] words = getAbstractSeq(oriExpression);//sequence is now initialised.if (words.length == 1) {System.out.println((turn++) + " : 正确 值为" + words[0]);continue;}char[] stack = new char[sequence.length()];int top = -1;char[] queue = sequence.toCharArray();int front = 1;stack[++top] = '#';int expression_state;while (true) {char curWord = queue[front];char topWord = '.';int near = top;for (; near >= 0; --near) {if (VT.indexOf(stack[near]) >= 0) {topWord = stack[near];break;}}if (topWord == '.') {expression_state = EXPRESSION_WRONG;outputBuffer.append("未找到离栈顶最近的VT");break;}if (curWord == '#' && topWord == '#') {expression_state = EXPRESSION_ACCEPT;break;} else {String key = topWord + " " + curWord;if (!table.containsKey(key)) {expression_state = EXPRESSION_WRONG;outputBuffer.append("错误单词为:" + words[front - 1]);break;} else {if (table.get(key) <= 0) {          //移进或者相等stack[++top] = curWord;++front;continue;} else {//栈顶规约int start = near - 1;       //start是near之前的Vt的下标while (true) {if (start < 0) {expression_state = EXPRESSION_WRONG;outputBuffer.append("规约过程失败");break;}if (VT.indexOf(stack[start]) < 0) {--start;} else {                //查表String key1 = stack[start] + " " + stack[near];if (table.get(key1) == SHIFT) {String result = reduceTable.get(String.valueOf(stack, start + 1, top - start));if (result == null) {expression_state = EXPRESSION_WRONG;outputBuffer.append("错误单词为:" + words[front - 1]);break;}//对要规约的单词进行检查int wrong = -1;for (int i = start + 1; i <= top; ++i) {if (!checkWhenReduce(stack[i], stack, i, top, start + 1)) {wrong = i;break;}}if (wrong != -1) {expression_state = EXPRESSION_WRONG;outputBuffer.append("错误单词为 " + stack[wrong]);break;}top = start;for (int i = 0; i < result.length(); ++i)stack[++top] = result.charAt(i);break;} else {near = start;--start;}}}}}}}if (expression_state == EXPRESSION_ACCEPT) {//writer.write("正确 逆波兰式为 " + getReversePolishExpression(words, value) + " 其值为" + value.value + '\n');String expression = getReversePolishExpression(words);System.out.println((turn++) + " : 正确 逆波兰式为 " + expression + " 其值为 " + getReversedPolishValue(expression));} else {//writer.write("错误 错误位置是" + outputBuffer.toString() + '\n');System.out.println((turn++) + " : 错误 " + outputBuffer.toString());}}scanner.close();//writer.close();}private void init() {table = new HashMap<>();table.put("# +", SHIFT);table.put("# -", SHIFT);table.put("# *", SHIFT);table.put("# /", SHIFT);table.put("# (", SHIFT);table.put("# i", SHIFT);table.put("+ *", SHIFT);table.put("+ /", SHIFT);table.put("+ (", SHIFT);table.put("+ i", SHIFT);table.put("- *", SHIFT);table.put("- /", SHIFT);table.put("- (", SHIFT);table.put("- i", SHIFT);table.put("* i", SHIFT);table.put("* (", SHIFT);table.put("/ (", SHIFT);table.put("/ i", SHIFT);table.put("( +", SHIFT);table.put("( -", SHIFT);table.put("( *", SHIFT);table.put("( /", SHIFT);table.put("( (", SHIFT);table.put("( i", SHIFT);table.put("+ #", REDUCE);table.put("+ +", REDUCE);table.put("+ -", REDUCE);table.put("+ )", REDUCE);table.put("- #", REDUCE);table.put("- +", REDUCE);table.put("- -", REDUCE);table.put("- )", REDUCE);table.put("* #", REDUCE);table.put("* +", REDUCE);table.put("* -", REDUCE);table.put("* *", REDUCE);table.put("* /", REDUCE);table.put("* )", REDUCE);table.put("/ #", REDUCE);table.put("/ +", REDUCE);table.put("/ -", REDUCE);table.put("/ *", REDUCE);table.put("/ /", REDUCE);table.put("/ )", REDUCE);table.put(") #", REDUCE);table.put(") +", REDUCE);table.put(") -", REDUCE);table.put(") *", REDUCE);table.put(") /", REDUCE);table.put(") )", REDUCE);table.put("i #", REDUCE);table.put("i +", REDUCE);table.put("i -", REDUCE);table.put("i *", REDUCE);table.put("i /", REDUCE);table.put("i )", REDUCE);table.put("# #", EQUAL);table.put("( )", EQUAL);operatorPriorityTable = new HashMap<>();operatorPriorityTable.put('+', 1);operatorPriorityTable.put('-', 1);operatorPriorityTable.put('/', 2);operatorPriorityTable.put('*', 2);operatorPriorityTable.put('(', 0);operatorPriorityTable.put(')', 4);reduceTable = new HashMap<>();reduceTable.put("#X#", "X");reduceTable.put("X+X", "X");reduceTable.put("X-X", "X");reduceTable.put("X", "X");reduceTable.put("X*X", "X");reduceTable.put("X/X", "X");reduceTable.put("(X)", "X");reduceTable.put("i", "X");}private boolean checkWhenReduce(char w, char[] stack, int pos, int upper, int bottom) {if (w == 'i') {if ((pos + 1 <= upper && stack[pos + 1] == 'X') && (pos - 1 >= upper && stack[pos - 1] == 'X')) {return false;}} else if (w == ')') { //往前查找boolean flag = false;//是否遇到（for (int i = pos - 1; i >= bottom; --i) {if (!flag && stack[i] == 'X')return false;else if (stack[i] == ')') continue;else return true;}} else if (w == '(') {return true;} else {if ((pos - 1 >= bottom && stack[pos - 1] != 'X') || (pos + 1 <= upper && stack[pos + 1] != 'X'))return false;}return true;}//简单词法分析器private String[] getAbstractSeq(String originalExpression) {StringBuffer buffer = new StringBuffer();//buffer for result sequencebuffer.append('#');ArrayList<String> list = new ArrayList<>();char[] S = new char[100];int top = -1;for (int i = 0; i < originalExpression.length(); ++i) {char ch = originalExpression.charAt(i);if (isBlank(ch)) {continue;} else {if (VT.indexOf(ch) >= 0) {if (top != -1) {//If it's an operatorbuffer.append("i");buffer.append(ch);//clear the stackString number = new String(S, 0, top + 1);top = -1;list.add(number);//add the numberlist.add(String.valueOf(ch));//add the operator} else {buffer.append(ch);list.add(String.valueOf(ch));}} else {S[++top] = ch;}}}if (top != -1) {String number = new String(S, 0, top + 1);buffer.append("i");list.add(number);}buffer.append("#");sequence = buffer.toString();return list.toArray(new String[list.size()]);}private String getReversePolishExpression(String[] words) {StringBuffer output = new StringBuffer();char[] operatorStack = new char[words.length];int top = -1;for (int i = 0; i < words.length; ++i) {if (isWordOperator(words[i])) {/*char operator = words[i].charAt(0);while (operatorTop != -1 && getPriorityDifference(operator, operatorStack[operatorTop]) <= 0) {char poppedOperator = operatorStack[operatorTop--];output.append(poppedOperator + ' ');}*/char operator = words[i].charAt(0);if (operator == '(') {operatorStack[++top] = operator;} else if (operator == ')') {while (operatorStack[top] != '(') {output.append(operatorStack[top--] + " ");}top--;} else {//当（栈非空and栈顶不是开括号and栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作：将栈顶元素出栈输出while (top != -1 && operatorStack[top] != '(' && getPriorityDifference(operatorStack[top], operator) >= 0) {output.append(operatorStack[top--] + " ");}operatorStack[++top] = operator;}} else {output.append(words[i] + ' ');}}while (top != -1)output.append(operatorStack[top--] + " ");return output.toString();}private float getReversedPolishValue(String expression) {float[] stack = new float[expression.length()];int top = -1;String[] words = expression.split(" ");for (String s : words) {if (isWordOperator(s)) {float a = stack[top--];float b = stack[top--];switch (s) {case "+":stack[++top] = a + b;break;case "-":stack[++top] = b - a;break;case "*":stack[++top] = a * b;break;case "/":if (b == 0) {meetZero = true;return Float.MIN_VALUE;} else {stack[++top] = b / a;}break;}} else {stack[++top] = Float.valueOf(s);}}return stack[0];}/*判断两个优先符优先级关系*/private int getPriorityDifference(char c1, char c2) {return operatorPriorityTable.get(c1) - operatorPriorityTable.get(c2);}/*判断是否是空白*/private boolean isBlank(char ch) {if (ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r')return true;else return false;}private boolean isWordOperator(String word) {char c = word.charAt(0);if (c >= '0' && c <= '9') return false;else return true;}
}