如何确定表达式在堆栈中是否具有平衡括号?
How do I determine if an expression has balanced brackets in a stack?
所以我写了这段代码来确定表达式是否在堆栈中有平衡括号:
public static boolean isBalanced(String expr) {
StringStack stack = new StringStackRefBased();
try{
for (int i = 0; i<expr.length(); i++){
if (expr.charAt(i) == ('(')){
stack.push("(");
} else if (expr.charAt(i) == (')')){
stack.pop();
}
}
if (stack.isEmpty()){
return true;
} else {
return false;
}
} catch (StringStackException e) {
return false;
}
}
问题是即使表达式有平衡括号,堆栈仍会返回 false,所以我的代码有什么问题?
这是 StringStackRefBased
的代码
public class StringStackRefBased implements StringStack {
private StringNode head;
public boolean isEmpty(){
return head == null;
}
public void push(String item) throws StringStackException{
head = new StringNode(item);
}
public String pop() throws StringStackException{
String result = null;
if(isEmpty()){
throw new StringStackException("Empty Stack");
}
head.next = head;
return head.toString();
}
public String peek() throws StringStackException{
if (isEmpty()){
throw new StringStackException("Stack underflow");
}
return head.toString();
}
}
方法不错。如果我使用 Java 自己的堆栈:
class Main {
public static boolean isBalanced(String expr) {
Stack<String> stack = new Stack<>();
try{
for (int i = 0; i<expr.length(); i++){
if (expr.charAt(i) == ('(')){
stack.push("(");
} else if (expr.charAt(i) == (')')){
stack.pop();
}
}
if (stack.isEmpty()){
return true;
} else {
return false;
}
} catch (Exception e) {
return false;
}
}
public static void main(String[] args) {
System.out.println(isBalanced("("));
System.out.println(isBalanced("(()"));
System.out.println(isBalanced("())"));
System.out.println(isBalanced("((()))"));
System.out.println(isBalanced("(()())"));
}
}
将打印:
false
false
false
true
true
顺便说一句,您的 return 语句相当冗长,以这种方式使用异常是不好的做法。例外就是:一个例外(al case)。这是 IMO 更好:
public static boolean isBalanced(String expr) {
Stack<String> stack = new Stack<>();
for (int i = 0; i < expr.length(); i++) {
if (expr.charAt(i) == ('(')){
stack.push("(");
}
else if (expr.charAt(i) == (')')) {
if (stack.isEmpty()) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
这就是您的堆栈正常工作的方式:
class StringStack {
private StringNode head = null;
public boolean isEmpty(){
return head == null;
}
public void push(String item) {
StringNode oldHead = head;
head = new StringNode(item);
head.next = oldHead;
}
public String pop() throws StringStackException {
if (isEmpty()) {
throw new StringStackException("Empty Stack");
}
String result = head.item;
head = head.next;
return result;
}
public String peek() throws StringStackException {
if (isEmpty()) {
throw new StringStackException("Stack underflow");
}
return head.item;
}
static class StringNode {
String item;
StringNode next;
public StringNode(String item) {
this.item = item;
}
}
}
所以我写了这段代码来确定表达式是否在堆栈中有平衡括号:
public static boolean isBalanced(String expr) {
StringStack stack = new StringStackRefBased();
try{
for (int i = 0; i<expr.length(); i++){
if (expr.charAt(i) == ('(')){
stack.push("(");
} else if (expr.charAt(i) == (')')){
stack.pop();
}
}
if (stack.isEmpty()){
return true;
} else {
return false;
}
} catch (StringStackException e) {
return false;
}
}
问题是即使表达式有平衡括号,堆栈仍会返回 false,所以我的代码有什么问题?
这是 StringStackRefBased
public class StringStackRefBased implements StringStack {
private StringNode head;
public boolean isEmpty(){
return head == null;
}
public void push(String item) throws StringStackException{
head = new StringNode(item);
}
public String pop() throws StringStackException{
String result = null;
if(isEmpty()){
throw new StringStackException("Empty Stack");
}
head.next = head;
return head.toString();
}
public String peek() throws StringStackException{
if (isEmpty()){
throw new StringStackException("Stack underflow");
}
return head.toString();
}
}
方法不错。如果我使用 Java 自己的堆栈:
class Main {
public static boolean isBalanced(String expr) {
Stack<String> stack = new Stack<>();
try{
for (int i = 0; i<expr.length(); i++){
if (expr.charAt(i) == ('(')){
stack.push("(");
} else if (expr.charAt(i) == (')')){
stack.pop();
}
}
if (stack.isEmpty()){
return true;
} else {
return false;
}
} catch (Exception e) {
return false;
}
}
public static void main(String[] args) {
System.out.println(isBalanced("("));
System.out.println(isBalanced("(()"));
System.out.println(isBalanced("())"));
System.out.println(isBalanced("((()))"));
System.out.println(isBalanced("(()())"));
}
}
将打印:
false false false true true
顺便说一句,您的 return 语句相当冗长,以这种方式使用异常是不好的做法。例外就是:一个例外(al case)。这是 IMO 更好:
public static boolean isBalanced(String expr) {
Stack<String> stack = new Stack<>();
for (int i = 0; i < expr.length(); i++) {
if (expr.charAt(i) == ('(')){
stack.push("(");
}
else if (expr.charAt(i) == (')')) {
if (stack.isEmpty()) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
这就是您的堆栈正常工作的方式:
class StringStack {
private StringNode head = null;
public boolean isEmpty(){
return head == null;
}
public void push(String item) {
StringNode oldHead = head;
head = new StringNode(item);
head.next = oldHead;
}
public String pop() throws StringStackException {
if (isEmpty()) {
throw new StringStackException("Empty Stack");
}
String result = head.item;
head = head.next;
return result;
}
public String peek() throws StringStackException {
if (isEmpty()) {
throw new StringStackException("Stack underflow");
}
return head.item;
}
static class StringNode {
String item;
StringNode next;
public StringNode(String item) {
this.item = item;
}
}
}