Hello Internet. So the task is to create our own parser for a expression calculator. For Example:

Input: 3+2*1-6/3
Output: 3

Input: 3++2
Output: Invalid Expression

Input: -5+2
Output: -3

Input: 5--2
Output: 7

The code Here solves a part of the problem except that it has a fixed input and negative values cannot be solved, And I'm not quite sure yet if it really does solve the expression with operator precedence.
but I already modified it to get an input expression from the user.
and I've been wondering for hours how to implement the solving for negative values. help anyone?

here's the current code

``````    import java.util.*;

public class ExpressionParser
{
// Associativity constants for operators
private static final int LEFT_ASSOC  = 0;
private static final int RIGHT_ASSOC = 1;

// Operators
private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
static
{
// Map<"token", []{precendence, associativity}>
OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
}

// Test if token is an operator
private static boolean isOperator(String token)
{
return OPERATORS.containsKey(token);
}

// Test associativity of operator token
private static boolean isAssociative(String token, int type)
{
if (!isOperator(token))
{
throw new IllegalArgumentException("Invalid token: " + token);
}

if (OPERATORS.get(token)[1] == type) {
return true;
}
return false;
}

// Compare precedence of operators.
private static final int cmpPrecedence(String token1, String token2)
{
if (!isOperator(token1) || !isOperator(token2))
{
throw new IllegalArgumentException("Invalid tokens: " + token1
+ " " + token2);
}
return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
}

// Convert infix expression format into reverse Polish notation
public static String[] expToRPN(String[] inputTokens)
{
ArrayList<String> out = new ArrayList<String>();
Stack<String> stack = new Stack<String>();

// For each token
for (String token : inputTokens)
{
// If token is an operator
if (isOperator(token))
{
// While stack not empty AND stack top element
// is an operator
while (!stack.empty() && isOperator(stack.peek()))
{
if ((isAssociative(token, LEFT_ASSOC)         &&
cmpPrecedence(token, stack.peek()) <= 0) ||
(isAssociative(token, RIGHT_ASSOC)        &&
cmpPrecedence(token, stack.peek()) < 0))
{
continue;
}
break;
}
// Push the new operator on the stack
stack.push(token);
}
// If token is a left bracket '('
else if (token.equals("("))
{
stack.push(token);  //
}
// If token is a right bracket ')'
else if (token.equals(")"))
{
while (!stack.empty() && !stack.peek().equals("("))
{
}
stack.pop();
}
// If token is a number
else
{
//  if(!isOperator(stack.peek())){
//      }
}
}
while (!stack.empty())
{
}
String[] output = new String[out.size()];
return out.toArray(output);
}

public static double RPNtoDouble(String[] tokens)
{
Stack<String> stack = new Stack<String>();

// For each token
for (String token : tokens) //for each
{
// If the token is a value push it onto the stack
if (!isOperator(token))
{
stack.push(token);
}
else
{
// Token is an operator: pop top two entries
Double d2 = Double.valueOf( stack.pop() );
Double d1 = Double.valueOf( stack.pop() );

//Get the result
Double result = token.compareTo("*") == 0 ? d1 * d2 :
token.compareTo("/") == 0 ? d1 / d2 :
token.compareTo("+") == 0 ? d1 + d2 :
d1 - d2;
// Push result onto stack
stack.push( String.valueOf( result ));
}
}

return Double.valueOf(stack.pop());
}

public static void main(String[] args) throws Exception{
Scanner in = new Scanner(System.in);
String reg = "((?<=[<=|>=|==|\\+|\\*|\\-|<|>|/|=])|(?=[<=|>=|==|\\+|\\*|\\-|<|>|/|=]))";
while(true){
try{
//String[] input = "( 1 + 2 ) * ( 3 / 4 ) - ( 5 + 6 )".split(" ");
String[] input =  in.nextLine() .split(reg);
String[] output = expToRPN(input);

// Build output RPN string minus the commas
System.out.print("Stack: ");
for (String token : output) {
System.out.print("[ ");System.out.print(token + " "); System.out.print("]");
}
System.out.println(" ");
// Feed the RPN string to RPNtoDouble to give result
Double result = RPNtoDouble( output );
}catch (NumberFormatException | EmptyStackException nfe){
System.out.println("INVALID EXPRESSION"); }
}
}
}
``````

The first problem I see here is that you use split() method from String class to obtain tokens. This is causing the bug you are having right now. If you look at your regex, you will see that the split() will consume the leading negative sign.

I would suggest you to parse the input string by yourself (using a grammar as your base knowledge). Implement a static method inside your class, take in a string, and return tokens as its result. The tokens should be defined by your grammar. Once you can get all your tokens properly, you then could move on to parse an expression.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.