Continueing with 数据结构和算法&刷题题记 but should be writen in English. This is an article for optimizing process on the algorithm compare to the previous.
DFA: The fixed format input can be resolved by DFA(deterministic finite automaton). The No.65 Valid Number is a classic example, so do as the complier. The essence is tranfering the status to next definited position that present the next action. If matched, then take action otherwise stop and quit from the process.
private int[][] DFAtable = new int[][]{
// 43.5e34 // /+-/0-9/./Ee/end { 0, 1, 2, 3,-1}//0 begin ,{-1,-1, 2,-1,-1}//1 +- ,{ 8,-1, 2, 3, 5}//2 number ,{-1,-1, 4,-1,-1}//3 . ,{ 8,-1, 4,-1, 5}//4 number ,{-1,-1, 6,-1,-1}//5 Ee ,{ 8, 7, 6,-1,-1}//6 number ,{ 8,-1, 6,-1,-1}//7 +- ,{ 8,-1,-1,-1,-1}//8 end };
The benefits is that the DFA is more clear and apparent than the previous method due to the table directs the whole process. The weekness is the table may be difficult to understand.
Recursion
Mostly, the recursion process would much fast to cost less. But consider the each invoking stack costs at least 4KB by memory. If the input is too complex to accomandate the whole stacks, the program will throw error as out of memory. To reduce the memory occupation, reassemble the call stacks will provide more space for calculation. The No.224 is well to demonstrate the process.
public static void main(String[] args) { String str = "(1+(4+2+(5+2))-3)+(6+8)"; System.out.println(new LT_224().calculate(str)); System.out.println(new LT_224().calculateIndex(str, 0)); } public int calculate(String s) { Stack<Integer> valueStack = new Stack<Integer>(); Stack<Integer> oprandStack = new Stack<Integer>(); return calculateStackIndex(s, valueStack, oprandStack); } private int calculateStackIndex(String s, Stack<Integer> valueStack, Stack<Integer> oprandStack) { int value=0; for(int oprand=1,tmp=0, start=0; start<s.length(); start+=1) { switch(s.charAt(start)) { case ‘(‘: valueStack.push(value);value=0; oprandStack.push(oprand);oprand=1; continue; case ‘)‘: value=valueStack.pop()+(oprandStack.pop()*value); continue; case ‘+‘: oprand= 1; continue; case ‘-‘: oprand=-1; continue; default: for(int j=start; j<s.length()&&‘0‘<s.charAt(j)&&s.charAt(j)<‘9‘; j+=1) { tmp+=tmp*10+(s.charAt(j)-‘0‘); start=j; } value += oprand*tmp;tmp=0; continue; } } return value; } private int index = 0; private int calculateIndex(String s, int start) { int value=0; for(int oprand=1,tmp=0; start<s.length(); start+=1) { switch(s.charAt(start)) { case ‘(‘: value+=oprand*calculateIndex(s, start+1); start=index; continue; case ‘)‘: index=start; return value; case ‘+‘: oprand= 1; continue; case ‘-‘: oprand=-1; continue; default: for(int j=start; j<s.length()&&‘0‘<s.charAt(j)&&s.charAt(j)<‘9‘; j+=1) { tmp+=tmp*10+(s.charAt(j)-‘0‘); start=j; } value += oprand*tmp;tmp=0; continue; } } return value; }
Advanced optimization for algorithms and data structure in programming.
原文：https://www.cnblogs.com/prospector/p/14241479.html