Estou a tentar fazer um programa para balencear parenteses…mas apesar de não ter erros, não funciona bem. Em todos os casos ele diz que a expressão está bem balenciada :roll:
Envio-vos o meu código. Alguém me poderia ajudar?
Obrigado.
public interface Stack
{
public Object push(int i);
public Object pop();
public boolean isEmpty();
}
class PilhaArray implements Stack
{
Object[] pilha;
int inicio;
public PilhaArray()
{
pilha = new Object[100];
inicio=-1;
}
public boolean isEmpty()
{
return inicio == -1;
}
public Object push(int item)
{
if (inicio==pilha.length-1)
{
pilha[++inicio] = item;
}
return item;
}
public Object pop()
{
if(!isEmpty())
{
inicio--;
}
return pilha[inicio];
}
}
import java.io.*;
public class BalenPararenteses
{
public static boolean verificarParen(String s)
{
PilhaArray stack = new PilhaArray ();
for (int i = 0; i < s.length()-1; i++)
{
switch (s.charAt(i))
{
case '(':
stack.push(new Character ('('));
break;
case '[':
stack.push(new Character ('['));
break;
case '{':
stack.push(new Character ('{'));
break;
case ')':
Character c = (Character) stack.pop();
if (!match(c.charValue(), s.charAt(i))) return false;
break;
case ']':
c = (Character) stack.pop();
if (!match(c.charValue(), s.charAt(i))) return false;
break;
case '}':
c = (Character) stack.pop();
if (!match(c.charValue(), s.charAt(i))) return false;
break;
default:
break;
}
}
if ( stack.isEmpty())
return true;
else
return false ;
}
public static boolean match(char lpar, char rpar) {
switch (lpar) {
case '(': return rpar == ')';
case '[': return rpar == ']';
case '{': return rpar == '}';
default: return false;
}
}
public static void main(String[] args) throws IOException
{
BufferedReader stdr;
stdr = new BufferedReader(new InputStreamReader(System.in));
String line = stdr.readLine();
while (line != null) {
if (verificarParen(line))
System.out.println("well parenthesized");
else
System.out.println("parenthesis mismatch");
line = stdr.readLine();
}
}
}
Algumas observações: Já existe uma classe Stack em java (java.util.Stack) que faz a mesma coisa que a tua classe PilhaArray. veja as observações que eu fiz no meio do código
public interface Stack {
//return void: o retorno não era usado para nada
//int para Character porque estava dando ClassCastException com o int
public void push(Character i);
//character para não ter que ficar fazendo cast
public Character pop();
public boolean isEmpty();
}[/code]
[code]class PilhaArray implements Stack {
private Character[] pilha;
private int inicio;
public PilhaArray() {
pilha = new Character[100];
inicio = -1;
}
public boolean isEmpty() {
return inicio == -1;
}
public void push(Character item) {
//você está apenas colocando, não tem que ter condição para colocar, apenas coloque :)
pilha[++inicio] = item;
}
public Character pop() {
//verificar para evitar IndexO...Exception
if (!isEmpty()) {
return pilha[inicio--];
}
else {
return null;
}
}
}
PilhaArray stack = new PilhaArray();
for (int i = 0; i < s.length() - 1; i++) {
switch (s.charAt(i)) {
case '(':
stack.push(new Character('('));
break;
case '[':
stack.push(new Character('['));
break;
case '{':
stack.push(new Character('{'));
break;
case ')':
//não precisa mais de cast
Character c = stack.pop();
//se for diferente de null eh pq tem mais parenteses fechando doque abrindo
if (c == null || !match(c.charValue(), s.charAt(i))){
return false;
}
break;
case ']':
c = stack.pop();
if (c == null || !match(c.charValue(), s.charAt(i))){
return false;
}
break;
case '}':
c = stack.pop();
if (c == null || !match(c.charValue(), s.charAt(i))) return false;
break;
default:
break;
}
}
if (stack.isEmpty()) {
return true;
}
else {
return false;
}
}
public static boolean match(char lpar, char rpar) {
switch (lpar) {
case '(':
return rpar == ')';
case '[':
return rpar == ']';
case '{':
return rpar == '}';
default:
return false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader stdr = new BufferedReader(new InputStreamReader(System.in));
String line = stdr.readLine();
while (line != null) {
if (verificarParen(line)) {
System.out.println("well parenthesized");
}
else {
System.out.println("parenthesis mismatch");
}
line = stdr.readLine();
}
E como eu realmente não tinha o que fazer, eu refiz o teu programinha de uma maneira, digamos, mais java 5
obs: eu tirei as outras classe porque, como eu disse, já existe uma que faz isso.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class BalenPararenteses {
private static final List<Character> abridores = new ArrayList<Character>(Arrays.asList('(', '[', '{'));
private static final List<Character> fechadores = new ArrayList<Character>(Arrays.asList(')', ']', '}'));
public static boolean verificarParen(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
//se o caractere esta abrindo
if (abridores.contains(c)) {
stack.push(c);
}
//se o caractere esta dechando
else if (fechadores.contains(c)) {
if(stack.isEmpty()){
//se está vazio é porque está fechando mais que abrindo
return false;
}
Character abridorCorrespondente = abridores.get(fechadores.indexOf(c));
if (!abridorCorrespondente.equals(stack.pop())) {
return false;
}
}
}
return stack.isEmpty();
}
public static void main(String[] args) throws IOException {
BufferedReader stdr = new BufferedReader(new InputStreamReader(System.in));
String line;
do{
line = stdr.readLine();
if (verificarParen(line)) {
System.out.println("well parenthesized");
} else {
System.out.println("parenthesis mismatch");
}
}
while (line != null);
}
}
Como a classe PilhaArray agora está correcta, pensei que não ia ter mais problemas por exemplo num programa que faça o calculo de uma expressao no formato postfix. Mas ele retorna um erro que não estou a conseguir corrigir. :roll:
Quando na excução ponho 5 9 8 + 4 6 * * 7 + *, ele retorna uma excepção:
Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: -1
at PilhaArray.pop(PilhaArray.java:
at Postfix.CalculPostFix(Postfix.java:
at Postfix.main(Postfix.java:
public class Postfix
{
public static void CalculPostFix(String s2)
{
PilhaArray s = new PilhaArray ();
for (int i = 0; i < s2.length(); i += 2)
{
if (s2.charAt(i) == '+')
s.push(s.pop() + s.pop());
else if (s2.charAt(i) == '*')
s.push(s.pop() * s.pop());
else
{
int num = 0;
do
{
num = num*10 + s2.charAt(i)-'0'; // Constrói número
++i;
}
while (s2.charAt(i) != ' ');
--i;
s.push(num);
}
}
System.out.println(s.pop());
}
public static void main(String[] args) throws IOException
{
BufferedReader stdr = new BufferedReader(new InputStreamReader(System.in));
String line = stdr.readLine();
CalculPostFix(line);
}
}[/code]
//INTERFACE STACK
public interface Stack
{
public void push(int i);
public int pop();
public boolean isEmpty();
}
[code]
//CLASSE PILHAARRAY
public class PilhaArray implements Stack
{
private int[] stack;
private int n;
public PilhaArray()
{
stack = new int[1000000];
n=-1;
}
public boolean isEmpty()
{
return n == -1;
}
public void push(int item)
{
stack[++n] = item;
}
public int pop() {
if (!isEmpty()) {
int item = stack[n--];
return item;}
}
Como eu disse, já existe uma classe que faz isso, e ela funciona direitinho. Veja o ultimo post que eu mandei, nele não é usado a sua PilhaArray. Eu uso java.util.Stack, você deveria usar ela também e esquecer essa PilhaArray.
