1. Member
Join Date
Mar 2011
Posts
12
Rep Power
0

## Mathematical Expression Validation

hi everyone! i'm new to this forum, and i'm having some "Logic trouble" in this problem...because i need to use stacks in validating the Mathematical Expression...and the problem goes in this condition:

1.) user will input the expression.
2.) use stacks
3.) and display if the expression is Valid or Invalid

any help would be appreciated! reach me thru this thread. Thanks in advance and more Power to this forum :)

2. Member
Join Date
Mar 2011
Location
Bulacan, Philippines
Posts
23
Rep Power
0
you can use regex to divide the math expression and then validate them

3. Just to help me out, show me a valid and invalid expression.

Do you know how a stack works? Push all the individual items on and then pop and test each item.

4. Member
Join Date
Mar 2011
Posts
12
Rep Power
0

actually i don't know how to implement that reg ex thingy...

my java knowledge is still @ nomad lvl haha :p

5. Member
Join Date
Mar 2011
Posts
12
Rep Power
0
a+b = Valid
c+b*a = Valid
a+ = Invalid
+a = Invalid

Expressions with Grouping symbols

(a+b)+c = Valid
(a+b+c = Invalid
a+c) = Invalid
(a+b)c = Invalid

6. Just push the whole thing onto the stack and pop it off and test each value, after each number the next item can only be a decimal, number or operator, after operators only a number or parenthesis.
Last edited by sunde887; 03-20-2011 at 11:47 AM.

7. Member
Join Date
Mar 2011
Posts
12
Rep Power
0
actually those are just examples of the User's input...if i set the parameters with those, my program will be limited to those expressions.

8. And that's just an example of how to do it, your code may have to account for more things, but if you are supposed to use a stack then the above should work, however; others may have better advice. This is my advice and I believe it should be a good start on solving this.

9. Member
Join Date
Mar 2011
Location
Bulacan, Philippines
Posts
23
Rep Power
0
String pattern="[0-9a-z[0-9a-z]]";
you can use that patten for checking the math expression on your sample expression

10. Member
Join Date
Mar 2011
Posts
12
Rep Power
0
but how can implement that with Stacks?

sorry for the noob questions...i'm not that great in Stacks and reg ex...

11. Member
Join Date
Mar 2011
Location
Bulacan, Philippines
Posts
23
Rep Power
0
there is already class stack included in java.

java.util.Stack;

12. Member
Join Date
Mar 2011
Location
Bulacan, Philippines
Posts
23
Rep Power
0
Java Code:
```import java.util.Stack;
public class Sample2 {

private Stack s=new Stack();
public static void main(String[] args) {

}
private void userInput(){
//do the userinput
s.push(userinput);
}
private void checkExpression(Stack s){
if(validExpression(s.pop().toString())){
System.out.println("Valid");
}else{
System.out.println("invalid");
}
}
private boolean validExpression(String s){
}
}```
your code may be look like this.. you must work on the logic and validating the expression

13. Originally Posted by FlemaVerde
actually those are just examples of the User's input...if i set the parameters with those, my program will be limited to those expressions.
To be more exact:

1) if the current input is a number or a left parenthesis push it on the stack;
2) if the current input is an operator, check the top two stack elements,
if they are numbers perform the operation and push the result back on the stack;
3) if the current input is a right parentesis, find a corresponding (topmost) left parenthesis on the stack and pop it.
4) if the input is empty check the stack: it should contain a single numeric result.

If any of the above operations fail the expression was syntactically invalid.

kind regards,

Jos

14. Member
Join Date
Mar 2011
Posts
12
Rep Power
0
tnx for the sample code...i'll try to work on the logic tnx a lot sir...hope to see your replies in my further questions! hehe

15. Member
Join Date
Mar 2011
Posts
12
Rep Power
0
Tnx Jos! i guess that answers all...but i really don't have any clue in making this kind of java program

16. Great response jos, that's what I was trying to convey(not nearly as well though)

@op: do you understand how to use a stack? Try making a small stack based program and work it to something more complex?

17. Originally Posted by FlemaVerde
Tnx Jos! i guess that answers all...but i really don't have any clue in making this kind of java program
Just for fun I'll post a small compiler that transforms an expression in infix notation to postfix notation; study it and you may use it for your own parser. Note that no tokenizer (lexical analyzer is included)

Java Code:
```public class PostfixCompiler {

public static boolean isOperator(char token) {

return "+-*/".indexOf(token) >= 0;
}

public static class PostfixException extends Exception {
PostfixException(String error) { super(error); }
}

private void pushLParen(StringBuffer stack) { stack.append('('); }

private void popLParen(StringBuffer stack, StringBuffer output)
throws PostfixException {

int i= stack.lastIndexOf("(");

if (i < 0) throw new PostfixException("unbalanced )");

int n= stack.length();
for (int j= n-1;  j > i; j--)
output.append(stack.charAt(j));

stack.delete(i, n);
}

private int getPriority(char token) {

switch (token) {
case '+':
case '-': return 1;
case '*':
case '/': return 2;
default : return 0;
}
}

private void doOperand(StringBuffer postfix, char token) {
postfix.append(token);
}

private void doOperator(StringBuffer stack, StringBuffer postfix, char token) {

int prioIn= getPriority(token);

for (int n= stack.length(); --n >= 0; stack.delete(n, n+1)) {
char stackToken= stack.charAt(n);
if (getPriority(stackToken) >= prioIn)
postfix.append(stackToken);
else
break;
}

stack.append(token);
}

private void flushStack(StringBuffer stack, StringBuffer postfix)
throws PostfixException {

for (int n= stack.length(); --n >= 0; stack.delete(n, n+1)) {
char stackToken= stack.charAt(n);
if (stackToken == '(')
throw new PostfixException("unbalanced (");
postfix.append(stackToken);
}
}

private boolean checkState(boolean operand, boolean state)
throws PostfixException {
if (operand != state)
throw new PostfixException((operand?"operand":"operator")+" expected");

return state;
}

public String compile(String expr) throws PostfixException {

StringBuffer stack= new StringBuffer();
StringBuffer postfix= new StringBuffer();

boolean operandState= true;

for (int i= 0, n= expr.length(); i < n; i++) {

char token= expr.charAt(i);

if (isOperator(token)) {
operandState= !checkState(operandState, false);
doOperator(stack, postfix, token);
}
else {
switch (token) {
case ')': operandState= checkState(operandState, false);
popLParen(stack, postfix);
break;

case '(': operandState= checkState(operandState, true);
pushLParen(stack);
break;

case ' ':
case '\t': break;

default : operandState= !checkState(operandState, true);
doOperand(postfix, token);
break;
}
}
}

flushStack(stack, postfix);

return postfix.toString();
}
}```
kind regards,

Jos

18. Member
Join Date
Mar 2011
Posts
12
Rep Power
0
--------------------Configuration: <Default>--------------------
java.lang.NoSuchMethodError: main
Process completed.

Tnx for the code jos! but it reflected those things...
Tnx for the continuous help brother :)

19. Originally Posted by FlemaVerde
--------------------Configuration: <Default>--------------------
java.lang.NoSuchMethodError: main
Process completed.

Tnx for the code jos! but it reflected those things...
Tnx for the continuous help brother :)
Of course, that class doesn't have a main method; you have to implement your own class with a main( ... ) method that constructs a PostfixCompiler, compiles your String; the return value of the compile( ... ) method is the postfix representation of the compiled expression. I can post a TreeCompiler that uses a PostfixCompiler and evaluates the tree (AST) it generated; if you want/need further spoonfeeding that is ;-)

kind regards,

Jos

20. Member
Join Date
Mar 2011
Posts
12
Rep Power
0
hi to all! i have made a program regarding my problem...and i only come up with character validation...hmmm and i guess i still need to check for the precedents, location of each char, and pairs of each grouping symbol...and honestly i don't know how to start those stuffs...the cod of my character validation is as follows:

Java Code:
```import java.util.*;

public class jed2{
public static void main(String[]args){
Scanner x = new Scanner(System.in);
Stack stack = new Stack();
String input = "";
int i = 0;
int j = 0;
int k = 0;
char allows[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m'
,'n','o','p','q','r','s','t','u','v','w','x','y','z','0','1','2'
,'3','4','5','6','7','8','9','+','-','*','/','(',')'};

System.out.print("Enter Expression: ");
input = x.nextLine();
if(input.contains(" ")){
System.out.print("Invalid!");
System.exit(0);
}
char inputArray[] = input.toCharArray();
for(i=0;i<inputArray.length;i++){
stack.push(input.charAt(i));
System.out.print(i);
}while(!stack.empty()){
for(j=0;j<input.length();j++){
for(k=0;k<allows.length;k++){
if(inputArray[j]==allows[k]){
System.out.print("Valid!");
System.exit(1);
}if(inputArray[j]!=allows[k]){
System.out.print("Invalid!");
System.exit(2);
}
}
}
}
}
}```

Page 1 of 2 12 Last

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•