题目:
代码及实现思路如下:
import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.Stack;
import java.util.Vector;
public class _4_6 {
public static void main(String[] args) {
/*
设计两个栈,S1和S2.
S1为int栈:
用于存放输入进来的"\"的位置,用i表示(输入数据时即可用于遍历,s.length(),s.charAt(i)).
如果遇到了"/",则计算i与栈顶数之差,并将栈顶数弹栈。
S2为Area类型的栈:
Area类包含一个记录最左侧"\"位置的pos(int)以及当前积水处的面积L(int)。
S2.size()就是积水处到的数量。
*/
//定义一个Area类型的类
class Area{
int pos;
int L;
Area(int pos, int L){
this.pos = pos;
this.L = L;
}
}
Scanner cin = new Scanner(new BufferedInputStream(System.in));
System.out.println("请输入一个水坝:(只能包含\\, _, /)");
String dam = cin.nextLine();
int N = dam.length();
Stack<Integer> S1 = new Stack<Integer>();
Stack<Area> S2 = new Stack<Area>();
for(int i=0;i<N;i++){
if(dam.charAt(i) == '\\'){
S1.push(i);
}
else if(dam.charAt(i) == '/'){
if(S1.size() == 0){continue;}//如果没有与之对应的\,那么这个位置的/无效,直接跳到下一个循环即可
else{
int square = i - S1.peek();//计算每一个小面积
//对S2进行操作
if(S2.size()==0){//如果栈为空,则直接压栈
Area new_area = new Area(S1.peek(), square);
S2.push(new_area);
}
else{
if(S2.peek().pos < S1.peek()){
//如果栈内面积涉及的\在新计算的面积的左边,说明两个凹槽不重叠,记录新的水坑面积,即执行压栈操作
Area new_area = new Area(S1.peek(), square);
S2.push(new_area);
}
else if(S2.peek().pos > S1.peek()){
//如果栈内面积涉及的\在新计算的面积的右边,说明两个凹槽重叠,合并水坑面积,并记录更新新位置;这个操作可能嵌套,要循环
Area new_area = new Area(S1.peek(), square);//用一个值来暂存最左侧的\和目前的面积值
while(S2.size()>0 && S2.peek().pos > S1.peek()) {
new_area = new Area(S1.peek(), S2.peek().L + new_area.L);//每次循环将面积值合并
S2.pop();
}
S2.push(new_area);
}
}
S1.pop();//计算完成后,将S1的位置弹栈
}
}
}/**/
Stack<Area> S3 = new Stack<Area>();
while(S2.size()!=0){
S3.push(S2.pop());
}
System.out.println("水坑数量有:" + S3.size());
System.out.println("每个水坑的面积分别为:");
while(S3.size()!=0){
System.out.println(S3.pop().L + " ");
}
}
}
// int sum = 0;
//
// for(int i=0;i<N;i++){
// if(dam.charAt(i) == '\\'){
// S1.push(i);//只要是“\”,就对S1执行入栈操作
// }
// else if(dam.charAt(i) == '/' && S1.size()>0){//如果是/,且S1栈内不为空
// int j = S1.peek();//记录S1栈顶的值
// S1.pop();//S1出栈
// sum+=i-j;
// int a = i-j;//记录小面积
// while (S2.size()>0 && S2.peek().pos>j){//只要S2不为空且S2的栈顶值大于S1的栈顶值
// a += S2.peek().L;
// S2.pop();
// }
// Area temp = new Area(j, a);
// S2.push(temp);
// }
// }
/*Vector<Integer> ans = new Vector<>();
while(S2.size()>0){ans.addElement(S2.peek().L);S2.pop();}*/
输入:
\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\
输出:
水坑数量有:5
每个水坑的面积分别为:
4
2
1
19
9