逆波兰计算器

首页 » 算法 » 逆波兰计算器

首先解释一下中缀转后缀表达式

中缀表达式是人类习惯理解的表达式, 但对于计算机来说后缀表达式更容易计算.   下面通过一个实例来介绍转换过程.


中缀表达式转后缀表达式具体步骤分析

1) 初始化两个栈: 运算符栈s1和储存中间结果的栈s2
2) 从左到右扫描中缀表达式
3) 遇到操作数时,将其压入s2
4) 遇到运算符时,比较其与s1栈顶运算符的优先级
1.如果s1为空或栈顶运算符为左括号“(”,则将此运算符入栈
2.否则,若优先级比栈顶运算符的高,也将运算符压入s1
3.否则,将s1栈顶的运算符弹出并压入s2中,再次转到4.1步
骤与s1中新的栈顶运算符进行比较
5) 遇到括号时:
1.如果时左括号"(",则直接压入s1
2.如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,
直到遇到左括号为止,此时将这一对括号丢掉
6) 重复步骤2至5,直到表达式的最右边
7) 将s1中剩余的运算符依次弹出并压入s2
8) 依次弹出s2中的元素并输出,结果的逆序就是中缀转后缀
的结果

实例: 1+((2+3)*4)-5=16

转换过程如下表.

扫描的元素s2s1说明
11数字,直接入栈
+1+s1为空,运算符直接入栈
(1+(左括号,直接入栈
(1+((左括号,直接入栈
21 2+((数字,直接入栈
+1 2+((+s1栈顶为左括号,运算符直接入栈
31 2 3+((+数字直接入栈
)1 2 3 ++(右括号,弹出运算符直到遇到左括号
*1 2 3 ++(*s1栈顶为左括号,运算符直接入栈
41 2 3 + 4+(*数字直接入栈
)1 2 3 + 4 *+右括号,弹出运算符直到遇到左括号
123+4*+-与+优先级相同,因此弹出+,再压入-
5123+4*+5数字直接入栈
到达最右端123+4*+5-s1中剩余的

中缀转后缀

public static List<String> houzhui(List<String> ls){//原串分别进栈
 Stack<String> s1=new Stack<String>();
 List<String> s2=new ArrayList<String>();
 for(String item:ls) {
  if(item.matches("\d+")) {//正则匹配数字
   s2.add(item);
  }else if(item.equals("(")){//步骤5.1
   s1.push(item);
  }else if(item.equals(")")){//步骤5.2
   while(!s1.isEmpty()&&!s1.peek().equals("(")) {
    s2.add(s1.pop());
   }
   s1.pop();//丢掉栈顶的“(”
  }else {
   while(!s1.isEmpty() && you(s1.peek())>=you(item)) {//步骤4.3
    s2.add(s1.pop());
   }
   s1.push(item);//步骤4.2
  }
 }
 while(s1.size()!=0)
  s2.add(s1.pop());
 return s2;
}

 


通过后缀表达式进行计算

public static int jisuan(List<String> ls) {
 Stack<String> s1=new Stack<String>();
 for (String str: ls) {
  if(s1.isEmpty())
   s1.push(str);
  else if(str.matches("\d+")) {
   s1.push(str);
  }else {
   int a=Integer.parseInt(s1.pop());
   int b=Integer.parseInt(s1.pop());
   switch(str) {
   case "+":
    s1.push(""+(a+b));
    break;
   case "-":
    s1.push(""+(b-a));
    break;
   case "*":
    s1.push(""+(a*b));
    break;
   case "/":
    s1.push(""+(b/a));
    break;
   }
   
  }
 }
 return Integer.parseInt(s1.pop());
}

 


完整代码

package 栈;

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

public class 逆波兰计算器 {
public static void main(String[] args) {
 String str="1+((2+3)*4)-5";
 List list=zhuan(str);
 System.out.println("中缀表达式:"+list);
 System.out.println("后缀表达式:"+houzhui(list));
 System.out.println("结果:"+jisuan(houzhui(list)));
}
public static int jisuan(List<String> ls) {
 Stack<String> s1=new Stack<String>();
 for (String str: ls) {
  if(s1.isEmpty())
   s1.push(str);
  else if(str.matches("\d+")) {
   s1.push(str);
  }else {
   int a=Integer.parseInt(s1.pop());
   int b=Integer.parseInt(s1.pop());
   switch(str) {
   case "+":
    s1.push(""+(a+b));
    break;
   case "-":
    s1.push(""+(b-a));
    break;
   case "*":
    s1.push(""+(a*b));
    break;
   case "/":
    s1.push(""+(b/a));
    break;
   }
   
  }
 }
 return Integer.parseInt(s1.pop());
}
public static int you(String str) {//优先级
 switch (str) {
 case "+":
  return 1;
 case "-":
  return 1;
 case "*":
  return 2;
 case "/":
  return 2;
 default:
  return 0;
 }
}
public static List<String> houzhui(List<String> ls){//原串分别进栈
 Stack<String> s1=new Stack<String>();
 List<String> s2=new ArrayList<String>();
 for(String item:ls) {
  if(item.matches("\d+")) {//正则匹配数字
   s2.add(item);
  }else if(item.equals("(")){//步骤5.1
   s1.push(item);
  }else if(item.equals(")")){//步骤5.2
   while(!s1.isEmpty()&&!s1.peek().equals("(")) {
    s2.add(s1.pop());
   }
   s1.pop();//丢掉栈顶的“(”
  }else {
   while(!s1.isEmpty() && you(s1.peek())>=you(item)) {//步骤4.3
    s2.add(s1.pop());
   }
   s1.push(item);//步骤4.2
  }
 }
 while(s1.size()!=0)
  s2.add(s1.pop());
 return s2;
}
public static List zhuan(String s) {//原串转list
 String str;
 List<String> ls=new ArrayList<String>();
 int zhen=0;
 char c;
 do {
  if((c=s.charAt(zhen))<48 || (c=s.charAt(zhen))>57) {
   ls.add(""+c);
   zhen++;
  }else {
   str="";
   while(zhen<s.length() && (c=s.charAt(zhen))>=48 && (c=s.charAt(zhen))<=57) {
    str+=c;
    zhen++;
   }
   ls.add(str);
  }
 }while(zhen<s.length());
 return ls;
}
}

运行结果

逆波兰计算器
分享到:
赞(0) 打赏

评论 4

评论前必须登录!

 

  1. #1

    不错

    小蚯蚓6个月前 (03-27)
  2. #2

    挺明白的

    努力6个月前 (03-27)
  3. #3

    good厉害了

    笔记本6个月前 (03-28)
  4. #4

    good厉害了

    你哥6个月前 (03-28)

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00