栈的使用-
计算中缀表达式
要点
①算式数组expressionArr=[num,symbol,num,symbol,...,num,"end"]
②算式数值最后一个元素会被设置为符号“end”，作为算式结束标志。
②symbol符号的权重：^>*=/>+=->end>empty。
③创建数字栈numStack、符号栈symbolStack。
④符号栈为空时，调用pop()返回符号“empty”。
⑤符号empty不会参与运算，是为了确保栈symbolStack为空时，可以把符号压入栈中。
⑥符号symbol入栈前，如果判断是end，标识运算结束，跳出循环。
过程
①算式字符串expressionStr拆分成算式数组expressionArr。
②读取expressionArr中的元素，数字num进出numStack，符号symbol进出symbolStack。
③得出结果
代码
public class Expression {public static void main(String[] args){Utils utils=new Utils();String expressionStr="1+12*3/2^2-6*2";String[] expressionArr=utils.getExpressionArr(expressionStr);System.out.println(utils.getResult(expressionArr));}
}class Utils{private int point=0;private char[] symbolArr={'+','-','*','/','^'};private boolean isSymbol(char symbolOrNum){for(int i=0;i<symbolArr.length;i++){if(symbolArr[i]==symbolOrNum){return true;}}return false;}private String nextSymbol(String expressionStr){if(point==expressionStr.length()){point=0;return "end";}char symbol=expressionStr.charAt(point);point++;return String.valueOf(symbol);}private String nextNum(String expressionStr){int start=point;while(isSymbol(expressionStr.charAt(point))==false){point++;if(point==expressionStr.length()){break;}}int end=point;String num=expressionStr.substring(start,end);return num;}public String[] getExpressionArr(String expressionStr){String[] strArr=new String[20];String symbolOrNum="start";int index=0;while(symbolOrNum!="end"){strArr[index++]=nextNum(expressionStr);symbolOrNum=strArr[index++]=nextSymbol(expressionStr);}return strArr;}public int getWeight(String symbol){int weight;switch (symbol){case "+":weight=0;break;case "-":weight=0;break;case "*":weight=1;break;case "/":weight=1;break;case "^":weight=2;break;case "end":weight=-1;break;default:weight=-999;break;}return weight;}public boolean canPush(String toPushSymbol,String topSymbol){return getWeight(toPushSymbol)>=getWeight(topSymbol);//return getWeight(toPushSymbol)>=getWeight(topSymbol) 也可以}public String getResult(String[] expressionArr){ArrayStack numStack=new ArrayStack(10);ArrayStack symbolStack=new ArrayStack(10);int index=0;while(true){String pushNum=expressionArr[index++];numStack.push(pushNum);String topushSymbol=expressionArr[index++];String topSymbol=symbolStack.getLast();while(canPush(topushSymbol,topSymbol)==false){topSymbol=symbolStack.pop();double toPushNum=0;double secondNum=Double.parseDouble(numStack.pop());double firstNum=Double.parseDouble(numStack.pop());switch (topSymbol){case "+":toPushNum=firstNum+secondNum;break;case "-":toPushNum=firstNum-secondNum;break;case "*":toPushNum=firstNum*secondNum;break;case "/":toPushNum=firstNum/secondNum;break;case "^":toPushNum=Math.pow(firstNum,secondNum);break;}numStack.push(String.valueOf(toPushNum));topSymbol=symbolStack.getLast();}if(topushSymbol=="end"){break;}symbolStack.push(topushSymbol);}return numStack.pop();}
}
class ArrayStack{private int maxSize;private String[] stack;public int top=-1;public ArrayStack(int maxSize){this.maxSize=maxSize;stack=new String[this.maxSize];}public boolean isFull(){return this.top==this.maxSize-1;}public boolean isEmpty(){return this.top==-1;}public void push(String num){if(this.top==this.maxSize-1){System.out.println("栈已满");return;}top++;stack[top]=num;}public String pop(){if(this.top==-1){return "empty";}String value=stack[this.top];this.top--;return value;}public String getLast(){if(this.top==-1){return "empty";}String value=stack[this.top];return value;}public void showStack(){for(int i=0;i<=this.top;i++){System.out.print(this.stack[i]+" ");}System.out.println();}
}
运行结果
-2中缀表达式转后缀表达式
要点
栈symbolStack弹出符号topSymbol后，不进行计算，而是把符号topSymbol压入栈numStack。
代码
public class Expression {public static void main(String[] args){Utils utils=new Utils();String expressionStr="1+12*3/2^2-6*2";String[] expressionArr=utils.getExpressionArr(expressionStr);ArrayStack numStack= utils.getResult(expressionArr);for(;numStack.top>=0;){System.out.print(numStack.pop()+" ");}}
}
class Utils{private int point=0;private char[] symbolArr={'+','-','*','/','^'};private boolean isSymbol(char symbolOrNum){for(int i=0;i<symbolArr.length;i++){if(symbolArr[i]==symbolOrNum){return true;}}return false;}private String nextSymbol(String expressionStr){if(point==expressionStr.length()){point=0;return "end";}char symbol=expressionStr.charAt(point);point++;return String.valueOf(symbol);}private String nextNum(String expressionStr){int start=point;while(isSymbol(expressionStr.charAt(point))==false){point++;if(point==expressionStr.length()){break;}}int end=point;String num=expressionStr.substring(start,end);return num;}public String[] getExpressionArr(String expressionStr){String[] strArr=new String[20];String symbolOrNum="start";int index=0;while(symbolOrNum!="end"){strArr[index++]=nextNum(expressionStr);symbolOrNum=strArr[index++]=nextSymbol(expressionStr);}return strArr;}public int getWeight(String symbol){int weight;switch (symbol){case "+":weight=0;break;case "-":weight=0;break;case "*":weight=1;break;case "/":weight=1;break;case "^":weight=2;break;case "end":weight=-1;break;default:weight=-999;break;}return weight;}public boolean canPush(String toPushSymbol,String topSymbol){return getWeight(toPushSymbol)>=getWeight(topSymbol);}public ArrayStack getResult(String[] expressionArr){ArrayStack numStack=new ArrayStack(15);ArrayStack symbolStack=new ArrayStack(15);int index=0;while(true){String pushNum=expressionArr[index++];numStack.push(pushNum);String topushSymbol=expressionArr[index++];String topSymbol=symbolStack.getLast();while(canPush(topushSymbol,topSymbol)==false){topSymbol=symbolStack.pop();numStack.push(topSymbol);topSymbol=symbolStack.getLast();}if(topushSymbol=="end"){break;}symbolStack.push(topushSymbol);}return numStack;}
}
class ArrayStack{private int maxSize;private String[] stack;public int top=-1;public ArrayStack(int maxSize){this.maxSize=maxSize;stack=new String[this.maxSize];}public boolean isFull(){return this.top==this.maxSize-1;}public boolean isEmpty(){return this.top==-1;}public void push(String num){if(this.top==this.maxSize-1){System.out.println("栈已满");return;}top++;stack[top]=num;}public String pop(){if(this.top==-1){return "empty";}String value=stack[this.top];this.top--;return value;}public String getLast(){if(this.top==-1){return "empty";}String value=stack[this.top];return value;}public void showStack(){for(int i=0;i<=this.top;i++){System.out.print(this.stack[i]+" ");}System.out.println();}
}
运行结果
+ - * 2 6 * / ^ 2 2 3 12 1 
