给定一个只包含三种类型字符的字符串：’(‘、’)’ 和 ‘*’，编写一个函数来检查该字符串是否有效。

---

描述

给定一个只包含三种类型字符的字符串：’(‘、’)’ 和 ‘*’，编写一个函数来检查该字符串是否有效。我们通过以下规则定义字符串的有效性：

1. 任何左括号 ‘(‘ 必须有一个相应的右括号 ‘)’
2. 任何右括号 ‘)’ 必须有一个相应的左括号 ‘(‘
3. 左括号 ‘(‘ 必须在相应的右括号 ‘)’ 之前
4. ‘*’ 可以被视为单个右括号 ‘ )’ 或单个左括号 ‘(‘ 或空字符串
5. 空字符串也有效。

样例

样例1：输入：”()” 输出：true
样例2：输入：”(*)” 输出：true 解释：’*‘看做是空
样例3：输入：”(*))” 输出：true 解释: ‘*’ 当作’(‘

思路

遍历字符数组，遇到左括号，左括号索引放入左括号栈，遇到*号，索引放入star栈。当遇到右括号的时候，这就先优先从左括号出栈，如果左括号栈空了，再从star栈出栈。

需要注意，*(这个情况，他不是有效括号。基于这个问题，栈就不能单纯的存字符括号和*号了，必须存放索引，当遍历完后，需要比较索引。

代码

package lintcode;

import java.util.*;

public class Solution {
	public static boolean checkValidString(String s) {
		
		Stack<Integer> leftParenthesis=new Stack<> ();//左括号
		Stack<Integer> starParenthesis=new Stack<> ();//星号
		char []arr=s.toCharArray();
		
		for(int i=0;i<arr.length;i++) {
			if(arr[i]=='(')
				leftParenthesis.push(i);
			else if(arr[i]=='*')
				starParenthesis.push(i);
			else if(arr[i]==')') {
				if(!leftParenthesis.isEmpty())
					leftParenthesis.pop();
				else if(!starParenthesis.isEmpty())
					starParenthesis.pop();
				else
					return false;
			}
			else
				return false;
		}
		
		//遍历完字符数组后，需要判断左括号栈，和*栈了。针对*（这中情况,左括号在*号的右边
		while(!leftParenthesis.isEmpty()&&!starParenthesis.isEmpty()) {
			if(leftParenthesis.peek()>starParenthesis.peek())
				return false;
			else {
				leftParenthesis.pop();
				starParenthesis.pop();
			}
		}
		//最后只需要判断左括号是否有剩余。最后如果剩下的都是***,那都是有效括号空字符
		return leftParenthesis.isEmpty();
	}
	
	public static void main(String args[]){
		Scanner in=new Scanner(System.in);
		String s=in.nextLine();
		boolean k=checkValidString(s);
		System.out.print(k);		
	}
}

补充

Java Stack类

栈是Vector的一个子类，它实现了一个标准的后进先出的栈；

堆栈只定义了默认构造函数，用来创建一个空栈；

堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。

boolean empty() //测试堆栈是否为空。
Object peek()//查看堆栈顶部的对象，但不从堆栈中移除它。
Object pop()//移除堆栈顶部的对象，并作为此函数的值返回该对象。
Object push(Object element)//把项压入堆栈顶部。
int search(Object element)//返回对象在堆栈中的位置，以 1 为基数。

Java 输入输出流

Java的输出函数很简单，直接调用System类的out对象的print函数即可。

System.out.print(a);//输出变量a的值
System.out.print("214214");//输出字符串
System.out.print("123"+a);//混合输出字符串和变量值

Java的输入函数还是Scanner类最好用，它既可以读字符，也可以读字符串和整数。

import java.util.Scanner;
public static void main(String [] args) { 
         Scanner sc = new Scanner(System.in); 
         System.out.println("请输入你的姓名："); 
         String name = sc.nextLine(); 
         System.out.println("请输入你的年龄："); 
         int age = sc.nextInt(); 
         System.out.println("请输入你的工资："); 
         float salary = sc.nextFloat(); 
}