双栈法补全括号

前言

正好昨天是双十一,不知道大家都买了些什么.今年应我们老师的要求,十二期免息入手了一台卡西欧计算器…因为自己高中那台屏幕漏液了这次干脆就破费买了台功能多的.

第一次用卡西欧是在初中时候.之前接触的都是大家日常使用的那种普通计算器.可能还有”一 加 四 等于 五”还带喇叭,用上卡西欧后,就像发现了新大陆.因为它支持带括号计算了,题目上再多括号的嵌套只要正确它都能输入计算出结果.甚至支持带分式的处理得到结果也是分式.所以当年甚是好奇到底是怎么实现的其实用栈来处理就相当容易了

栈(stack)是一种遵循后进先出原则的数据结构.表尾是栈顶,表头则是栈底,其进栈(push)和出栈(pop)的操作都是在栈顶进行.我们在浏览网页时页面不停地跳转时,其中点击回退按钮后能够返回到上一页面的实现就是用到了栈的原理,计算机不停的将你当前浏览过的页面压入栈,在执行后退时在不停地弹出,这一顺序正好和你浏览过程相反.

这里不详细介绍栈的具体结构及实现方法,主要介绍双栈法

计算四则表达式

E.W.Dijkstra发明了一个算法,通过两个栈来实现一个带括号的算术表达式求值.

规定表达式是由括号,运算符,数字构成的字符串,其中运算符也只考虑四种基本的+,-,*,/.

创建两个栈,一个数字栈(vals),一个符号栈(ops),分别用来存放数字和符号

1
2
stack<Double> vals = new stack<>();
stack<String> ops = new stack<>();
  • 遇到数字进数字栈
  • 遇到运算符进符号栈
  • 遇到左括号忽略
  • 遇到右括号,分别在数字栈弹出两个数字,符号栈弹出一个符号进行计算,再将结果压入数字栈

最终数字栈只会留下最后一个值,就是该表达式的值,更加通用的处理方式还有将中序表达式转换成后序之后进行计算,这里不再展开.

补齐括号

题目来自算法第四版的练习1.3.9,原题:

编写一段程序,从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式.

例如:给定输入:

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

你的程序应该输出:

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

这个问题同样可以通过双栈法解决

和双栈法计算四则表达式一样,我们创建两个栈,分别存储数字和符号,不过现在我们不需要求值,而是直接输出补齐括号的表达式,所以我们数字栈也就改成存储字符串型

1
2
Stack<String> vals = new Stack<>();
Stack<String> opts = new Stack<>();

我们这样规定

  • 如果遇到符号,如”+,-,*,/“,压进符号栈 opts ,如果遇到数字,压进数字栈 vals
  • 如果遇到”)”,分别弹出两位数字栈 vals 和一位符号栈 opts 进行拼接,然后将拼接后的字符串压回数字栈 vals

过程

我们拿题目样例来演示这个过程1+2)*3-4)*5-6)))

前面3位的进栈没什么问题,接下来我们碰到了第一个”)”,按照我们的规则我们弹出数字栈的前两位以及符号栈的前一位进行一个拼接,红色部分就是栈中元素,同时在两端分别加上括号,形成一个新的字符串

同时我们将新的字符串压入到数字栈中

这部分对应代码,注意根据栈的后进先出原则,这里的先弹出n1是原表达式符号后的数字:

1
2
3
4
5
String n1 = vals.pop();
String n2 = vals.pop();
String opt = opts.pop();
String data = "(" + n2 + opt + n1 + ")";
vals.push(data)

接下来程序继续走,走到了第二个待补全的右括号

进行和刚才一样的操作,拼接出一个新的字符串并压入数字栈

继续走,走到第三个待补全的右括号,此时后面全是右括号了,

相同处理后,现在的数字的栈元素都变成了带括号的字符串,后面的处理也是相同的,将它们看作一个数字与操作符做拼接

进行倒数第二次拼接,并压入数字栈

最后一个右括号我们把数字栈中剩下的两个字符串和符号栈中的最后一个符号做拼接,得到了补全了左括号后的完整表达式,现在只要弹出结果就行了

实现

这里用的是 Java,主函数输出输出用的是算法四的函数

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
import edu.princeton.cs.algs4.*;

public class ex139{

public static String completeParentese(String in){
Stack<String> vals = new Stack<>();
Stack<String> opts = new Stack<>();

char[] s = in.toCharArray();
for (char ch : s){
if (ch == '*' || ch == '/' || ch == '+' || ch == '-'){
opts.push(String.valueOf(ch));
}
else if (ch == ')'){
String n1 = vals.pop();
String n2 = vals.pop();
String opt = opts.pop();
String data = "(" + n2 + opt + n1 + ")";
vals.push(data);
}
else
vals.push(String.valueOf(ch));
}
return vals.pop();
}
public static void main(String[] args) {
String st = StdIn.readString();
System.out.println(completeParentese(st));
}
}

Asahi
2019.11.12

Author

Asahi

Posted on

2019-11-13

Updated on

2022-09-23

Licensed under