每日一记
栈简单应用之符号匹配
关键：读括号时，如果时括号的左半部分（正常情况下，括号的左半部分总是先读到）,如果遇到括号的右半部分，获取栈顶元素，如果匹配则弹出栈，如果不匹配依旧弹栈且哨兵flag记为FALSE,最后如果flag为TRUE且栈不为空或是flag为FALSE且栈为空则符号不匹配，如果栈为空且flag为TRUE则符号匹配。
代码
package DEVIL.泛型与集合框架.堆栈;
import java.util.Scanner;
import java.util.Stack;
public class E_04 {
public static void main(String[] args){
Stack<Character> stack = new Stack<>();
Scanner sc = new Scanner(System.in);
boolean flag = true;
String str;
str = sc.nextLine();
for(int i = 0; i<str.length();i++){
char ch = str.charAt(i);
if(ch=='('||ch=='{'||ch=='['){
stack.push(ch);
}
else if(ch==')'&& !stack.empty()){
if(stack.peek() == '('){
stack.pop();
}else {
stack.pop();
flag = false;
break;
}
}
else if(ch=='}'&& !stack.empty()){
if(stack.peek() == '{'){
stack.pop();
}else{
stack.pop();
flag = false;
break;
}
}
else if(ch==']'&& !stack.empty()){
if(stack.peek() == '['){
stack.pop();
}else{
stack.pop();
flag = false;
break;
}
}
else if(stack.empty()){
flag = false;
break;
}
}
if(flag&&stack.empty()){
System.out.println("YES\n");
}
else{
System.out.println("NO\n");
}
sc.close();
}
}
|
输入样例1：
{(1+2)*3+4/(3-1)
控制台输出：
NO
输入样例2：
(1+2)*3+4/(3-1)
控制台输出：
YES
对称矩阵
对称矩阵可以将一个n * n存储空间的数组压缩成一个n(n+1)/2大小的数组* 一般拿一维数组存储。
接下来代码将展示一般对称矩阵压缩以及还原输出
代码
package 练习题;
import java.util.Scanner;
public class E_21 {
public static void main(String[] args) {
int n;
Scanner sc = new Scanner(System.in);
System.out.println("=======================输入数据==============================");
System.out.print("请输入一个n*n的矩阵的n:");
n = sc.nextInt();
System.out.println("请输入n*n矩阵的元素:");
int[][] Array = new int[n][n];
for(int i = 0; i<Array.length; i++){
for(int j=0; j<Array[i].length; j++){
Array[i][j]=sc.nextInt();
}
}
if(isSymmetricMatrix(Array)){
System.out.println("输入的矩阵是对称矩阵");
int[] SymmetricMatrix = new int[n*(n+1)/2];
int index = 0;
for(int i = 0; i<Array.length; i++){
for(int j=0; j<i+1; j++){
SymmetricMatrix[index++] = Array[i][j];
}
}
System.out.println("=======================输出压缩后的矩阵==============================");
for (int symmetricMatrix : SymmetricMatrix) {
System.out.print(symmetricMatrix+"\t");
}
System.out.println();
System.out.println("=========================还原对阵矩阵============================");
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i<j){
System.out.print(SymmetricMatrix[j*(j+1)/2+i]+"\t");
}
else{
System.out.print(SymmetricMatrix[i*(i+1)/2+j]+"\t");
}
}
System.out.println();
}
}
}
public static boolean isSymmetricMatrix(int[][] Array){
boolean flag = true;
for(int i = 0; i<Array.length; i++){
for (int j = 0; j<Array[i].length; j++){
if(Array[i][j]!=Array[j][i]){
flag = false;
break;
}
}
}
return flag;
}
}
|
还原对称矩阵时上三角部分：上三角部分的元素下标与压缩矩阵元素下标满足关系k = (j(j+1)/2+i) k为压缩矩阵元素下标*
还原对称矩阵时上三角部分：下三角以及对角线元素下标与压缩矩阵元素下标满足关系k = (j(j+1)/2+i)*
输入样例；
控制台输出：
=======================输入数据==============================
请输入一个n*n的矩阵的n:2
请输入n*n矩阵的元素:
1 2
2 1
输入的矩阵是对称矩阵
=======================输出压缩后的矩阵==============================
1 2 1
=========================还原对阵矩阵============================
1 2
2 1
|
接下来将展示输入一个已经压缩的对称矩阵将其还原输出
代码：
package 练习题;
import java.util.Scanner;
public class E_22 {
public static void main(String[] args) {
int n, row;
Scanner sc = new Scanner(System.in);
System.out.println("=======================输入数据==============================");
System.out.print("请输入压缩的对称矩阵的大小n:");
n = sc.nextInt();
System.out.println("请给出矩阵元素:");
int[] SymmetricMatrix = new int[n];
for(int i=0; i<n; i++){
SymmetricMatrix[i] = sc.nextInt();
}
System.out.println("\n======================输出压缩的对称矩阵======================");
for (int i = 0; i<n; i++) {
System.out.print(SymmetricMatrix[i]+"\t");
}
for(row = 0; row<n; row++){
if ((row*(row+1)/2)==n){
break;
}
}
System.out.println("\n======================还原输出对称矩阵======================");
for(int i = 0; i<row; i++){
for (int j=0; j<row; j++){
if(i<j){
System.out.print(SymmetricMatrix[j*(j+1)/2+i]+"\t");
}
else{
System.out.print(SymmetricMatrix[i*(i+1)/2+j]+"\t");
}
}
System.out.println();
}
}
}
|
输入样例：
10
1 2 3 4 5 6 7 8 9 10
控制台输出：
=======================输入数据==============================
请输入压缩的对称矩阵的大小n:10
请给出矩阵元素:
1 2 3 4 5 6 7 8 9 10
======================输出压缩的对称矩阵======================
1 2 3 4 5 6 7 8 9 10
======================还原输出对称矩阵======================
1 2 4 7
2 3 5 8
4 5 6 9
7 8 9 10
|
-end-
