算法4--双栈的利用<学习感悟>

最近在利用Java进行有关算法及背包、队和栈的数据结构学习，在利用双栈进行算数表达式求值和左括号补全的过程中，有一些感悟，于是记录下来同大家进行分享。

Dijkstra的双栈算术表达式求值算法

package com.algm4;
import java.util.Stack;

public class Dijkstra_double_stack { public static void main(String[] args) { // TODO Auto-generated method stub String str = new String ("(1+(2+3)*(4*5)))"); double cal_result = evl(str); System.out.print(cal_result); } public static Double evl(String str){ Stack<Double> vals = new Stack<Double>(); Stack<Character> op = new Stack<Character>(); char[] ch = str.toCharArray(); for(int i = 0;i < ch.length;i++){ if(ch[i] == '+') op.push(ch[i]); else if(ch[i] == '-') op.push(ch[i]); else if(ch[i] == '*') op.push(ch[i]); else if(ch[i] == '/') op.push(ch[i]); else if(ch[i] == '('); else if(ch[i] == ')'){ char o = op.pop(); Double val = vals.pop(); if(o == '+') val = val + vals.pop(); else if(o == '-') val = vals.pop() - val; else if(o == '*') val = vals.pop() * val; else if(o == '/') val = vals.pop() / val; vals.push(val); }else{ vals.push(Double.parseDouble(Character.toString(ch[i]))); } } return vals.pop(); }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

在这个双栈算数表达式求职算法中，利用两个栈分别存储运算数和运算符，并且根据检测右括号”）”来实现对之前运算数及预算符的计算行为触发。
而在左括号补齐习题中，同样可以用这种思路，将右括号出现之前的所有运算数和运算符号分别存入两个栈中，分别得到data1，opertator和data2，然后在检测到data2后面的)之后，生成一个”(“+data1+operator+data2+”)”，然后再将生成的全部内容作为data1压入数据栈中，注意，因为operator也被压入了数据栈中，所以数据栈的格式应当是String而非Double。重复迭代上述行为，就可以实现对于所有右括号，补全其左括号。根据这个方法，我编写了如下的测试程序并能够成功运行：

package com.algm4;
import java.util.Stack;

public class Cpt3_1_3_9 { public static void main(String[] args) { // TODO Auto-generated method stub String str = new String ("1+2)*3-4)*5-6)))"); String cal_result = fulfill(str); System.out.print(cal_result); } public static String fulfill(String str){ Stack<String> dataStack = new Stack<String>(); Stack<String> optrStack = new Stack<String>(); for (int i = 0; i < str.length(); i++) { if (isDigit(str.charAt(i))) { dataStack.push(String.valueOf(str.charAt(i))); } else if (isOpeartor(str.charAt(i))) { optrStack.push(String.valueOf(str.charAt(i))); } else { String d2 = dataStack.pop(); String d1 = dataStack.pop(); String opt = optrStack.pop(); String exstr = "(" + d1 + opt + d2 + ")"; dataStack.push(exstr); } } while (optrStack.size() > 0) { String opt = optrStack.pop(); String d2 = dataStack.pop(); String d1 = dataStack.pop(); String exstr = "(" + d1 + opt + d2 + ")"; dataStack.push(exstr); } return dataStack.pop(); } private static boolean isOpeartor(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } private static boolean isDigit(char ch) { return ch >= '0' && ch <= '9'; }

}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
 

console输出结果

((1+2)*((3-4)*(5-6)))

可见，这个算法很好地实现了补齐左括号的工作。

文章来源: zclhit.blog.csdn.net，作者：zclhit_，版权归原作者所有，如需转载，请联系作者。

原文链接：zclhit.blog.csdn.net/article/details/55510807