【数据结构】逆波兰表达式算法-Java版


这两天一直在看数据结构,栈这个地方,基础的就是这个逆波兰表达式,看了很多博文,都讲得不清不楚或者只能计算一个位的数字,决定自己写,这篇博文给了很大启发-->Go New Land AND Here

逆波兰简而言之是将中缀转换为后缀表达式,从而方便计算机进行四则运算,属于栈的基本运用

操作符优先级: ()    +-     */%(从左到右递增)

 

规则:

1.建立一个OP(操作栈),一个ArrayList(存储输出结果)

2.将字符串从左向右遍历,把数据放入ArrayList,把运算符压入运算符的栈

  关于运算符压栈的规则:⑴ 如果OP为空或者为待压栈操作符为左括号则直接将运算符压入栈

           ⑵ 如果待压栈操作符的优先级大于栈顶操作符则直接入栈

           ⑶ 如果待压栈操作符的优先级小于栈顶操作符,则将OP栈顶的操作符依次输出 直到遇到左括号或者OP为空则停止,此时压入该操作符到OP栈顶中

           ⑷ 如果遇到右括号则将OP栈中的元素依次弹出 输出 直到遇到左括号为止,同时弹出左括号不放入ArrayList,并且右括号不压入OP

           ⑸ 最后将OP中的元素依次弹出输出, 将ArrayList输出则是最终的逆波兰表达式

JAVA代码:

import java.util.ArrayList;
import java.util.Stack;


/**
 * 将中缀表达式转出后缀表达式,再计算其结果
 * 中缀表达式 9+(3-1)*3+10/2 = 20 转后缀931-3*+10 2/+
 */public class 栈逆波兰表达式 {

 public static void toOpArray(String x) {
 //存储输出的结果
 ArrayList operate =new ArrayList();
 //操作符的栈
 Stack stack = new Stack();
 //原始串
 StringBuffer oldString=new StringBuffer();

 char[] old = (x + " ").toCharArray();
 StringBuffer stringBuffer = new StringBuffer();
 for (char read : old) {
 //原始操作符分割 数字和操作符的区分
 if (read >= 48 && read <= 57) {
 stringBuffer.append(read);
 continue;
 } else {
 if (stringBuffer.length() != 0) {
 //存入数字操作符分隔好的原始表达式
 oldString.append(stringBuffer+" ");

 operate.add(Integer.valueOf(stringBuffer.toString()));
 stringBuffer.setLength(0);
 }
 }

 //最后的空格不参与计算
 if (read==' '){
 continue;
 }
 
 //存入数字操作符分隔好的原始表达式
 oldString.append(read+" ");

 //解析 OP为操作栈
 //⑴ 如果OP为空或者为待压栈操作符为左括号则直接将运算符压入栈
 if (stack.isEmpty()||read=='('){
 stack.push(read);
 //结束此次运算符操作
 continue;
 }

 //⑷ 如果遇到右括号则将OP栈中的元素依次弹出 输出至operate中直到遇到左括号为止,弹出左括号但不输出至operate 并且右括号不压入OP
 if (read==')'){
 //不为空则一直循环
 while (!stack.isEmpty()){
 char tmp= (char) stack.pop();
 //当遇到左括号 弹出并结束循环
 if (tmp=='('){
 break;
 }
 //否则输出到operate中
 operate.add(tmp);
 }
 continue;
 }

 //普通情况
 if (!stack.isEmpty()){
 char top= (char) stack.pop();
 int readPri=getPriority(read);
 int topPri=getPriority(top);
 //⑵ 如果待压栈操作符的优先级大于栈顶操作符则直接入栈
 if (readPri>topPri){
 //不要忘记将弹出的压入
 stack.push(top);
 stack.push(read);
 }else {
 //⑶ 如果栈顶操作符的优先级大于待压栈操作符,则将OP栈顶的操作符依次输出
 // 直到遇到左括号或者OP为空则停止,此时压入该操作符到OP栈顶中
 operate.add(top);
 while (true){
 if (!stack.isEmpty()){
 char tmp= (char) stack.pop();
 if (tmp=='('){
 stack.push(tmp);
 break;
 }
 operate.add(tmp);
 }else {
 break;
 }

 }
 stack.push(read);
 }
 }
 }

 //⑸ 最后将OP中的元素依次弹出并输出,则operate为最终的逆波兰表达式
 while (!stack.isEmpty()){
 operate.add(stack.pop());
 }
 //输出
 System.out.println("原始串:"+oldString);
 System.out.print("结果串:");
 for (int i = 0; i < operate.size(); i++) {
 System.out.print(operate.get(i) + " ");
 }
 //计算结果
 //getRes(operate);
 System.out.println("\n");
 }

 //() +- */ 优先级从小到大
 public static int getPriority(char read) {
 int pri = -1;
 switch (read) {
 case '+':
 pri = 1;
 break;
 case '-':
 pri = 1;
 break;
 case '*':
 pri = 2;
 break;
 case '/':
 pri = 2;
 break;
 case '(':
 pri = 0;
 break;
 case ')':
 pri = 0;
 break;
 }
 return pri;

 }

 public static void main(String[] args) {
 System.out.println("理论串:"+"9 3 1 - 3 * + 10 2 / +");
 toOpArray("90+(3-1)*3+10/2");
 toOpArray("9+10/2+(3-1)*3");
 toOpArray("10/2+(3-1)*3+90");
 }

}
//计算结果
private static void getRes(ArrayList operate) {
 Stack stack=new Stack();
 //因为我上面的逆波兰最后面带了一个空格 所以最后一个元素为空 不计算 这里减一
 for (int i = 0; i <operate.size()-1 ; i++) {
 if (operate.get(i).equals('+')||operate.get(i).equals('-')||operate.get(i).equals('*')||operate.get(i).equals('/')){
 //操作符处理
 char c= (char) operate.get(i);
 int b= (int) stack.pop();
 int a= (int) stack.pop();
 switch (c){
 case '+':
 stack.push(a+b);
 break;
 case '-':
 stack.push(a-b);
 break;
 case '*':
 stack.push(a*b);
 break;
 case '/':
 stack.push(a/b);
 break;
 }
 }
 else {
 //数字压栈
 stack.push(operate.get(i));
 }
 }
 System.out.println("结果为:"+stack.pop());
 System.out.println();
}

看了规则,写一遍代码,就可以理解了。

当然,我这个也没处理负数,没处理被除数为0的情况

大概思路:

负数:当遇到一个操作符() + - * / 第二次如果依旧为操作字符而且为-时 下个数字做负数处理

被除数为0:遇到/后,判断下个数字是否为0,为0则抛出异常

发现一个bug:

(24*1+(4+6)*2) + (4-3*2)*(4+6-9+(11-3*4)*2+2)*10+20-3*2*4+2 会是1738
(24*1+(4+6)*2) 是44
 (4-3*2)*(4+6-9+(11-3*4)*2+2)*10+20-3*2*4+2 是-22
 
 没能找到原因,待高手指点。

声明:TIL|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA[ZH]协议进行授权

转载:转载请注明原文链接 - 【数据结构】逆波兰表达式算法-Java版


Life is very interesting. In the end, some of your greatest pains become your greatest strengths.