DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Coding
  3. Languages
  4. Evaluating Infix Expression With Parentheses in Groovy - Multiple Digits

Evaluating Infix Expression With Parentheses in Groovy - Multiple Digits

Arun Manivannan user avatar by
Arun Manivannan
·
Oct. 26, 12 · Interview
Like (0)
Save
Tweet
Share
9.13K Views

Join the DZone community and get the full member experience.

Join For Free

When I wrote this write-up on evaluating an infix expression having multiple digits, I was lazy to do it for expressions with parentheses. So, here it comes.

As usual, here is the javascript version.

Just like the non-paranthesized version, this algorithm is just the two stack algorithm modified to accommodate parentheses and multiple digits. Floating points aren’t supported intentionally nor is tested. However, I don’t see any reason why it should not work (provided you change the variable types to accommodate a floating point number).

The algorithm goes like this :

1. Initialize two stacks - one for holding values and one for holding operators
2. Read the input expression from left to right - one character at a time. 
3. If the character is a space, ignore
4. If the character is a number, then append it to an accumulating variable 
   (don't push it to the stack yet)
5. If the character is an operator or a right parenthesis, push the accumulated number 
   to the value stack and reinitialize the accumulator.

    5a. If the current operator is a left parenthesis, push it to the expression stack 
        and continue to the next character in the expression. 

    5b. If the current operator is a right parenthesis, then evaluate the stacks 
        until the first left parenthesis is reached. Push the result back to the value stack 

    5b. If the current operator is of higher precedence than the first item in the operator stack,
        then safely ignore and read further. 

    5c. If the current operator is of lower precedence than the first item in the operator 
        stack (peek view), then evaluate the previous set (two from value stack and one 
        from operator stack) and insert the result into the value stack

    5d. Finally, insert the current operator to the operator stack

Note : the operator level for right parenthesis is kept at ‘0’ to retain operator precedence while the operator level of left paranthesis is kept at ‘3’ (or anything higher than all the operators) to be the least in the precedence. The only purpose of storing the left brackets in the expression stack is for identifying the beginning of the paranthesized sub-expression.

public static final Map OPERATOR_LEVELS= [")":0, "*":1, "/":1, "+":2,"-":2, "(":3]

A Groovy implementation is here :

/**
* Only basic arithmetic operators are supported. However, could easily be
* extended to support any binary operators
*
* This program is not an infix to postfix converter. However, this program does the following
*
* 1) Evaluates a parenthesized or non-parenthesized infix expression and drives it to a final value
* 2) Supports parentheses
* 3) Supports multiple digits as operands
* 4) Empty space allowed
* 5) Floating point numbers not supported by intent
* 6) Supports only the 4 basic arithmetic operators but could easily be extended to support any other
* binary operation
*
* @author Arun Manivannan
*/



public class InfixToValueParenthesis {


    public static final String OPERATORS="+-/*()" //ignore the "(" as an operator
    public static final Map OPERATOR_LEVELS= [")":0, "*":1, "/":1, "+":2,"-":2, "(":3]

    public static void main(String[] args) {

        String inputExpression="((10 - 5)*(3+6))*2+3" //610
        InfixToValueParenthesis ifixToPfix=new InfixToValueParenthesis()
        ifixToPfix.infixToValue(inputExpression);
    }

    def infixToValue(String inputExpression) {
        Stack<String> expressionStack = new Stack<String>()
        Stack<Long> valueStack = new ArrayDeque<Long>() //to hold only non-decimal values

        String eachNumber="" //to hold multiple digit values. lame idea, i know, but can't think of anything else at 2 AM

        int totalCharInInput=inputExpression.length()

        inputExpression.each { eachChar->
            totalCharInInput--

            println ("each char : "+eachChar)

            if (eachChar.trim()==""){
                 //ignore
            }
            else if (isValidOperator(eachChar)){


                //We could stack up a lot of left parenthesis in the beginning without reaching a number. Weed it out
                if (!isLeftParen(eachChar) && eachNumber.isNumber()){
                    valueStack.push(Long.parseLong(eachNumber)) //push the till now accumulated number to the value stack
                    eachNumber=""
                }

                if (expressionStack.isEmpty() || isLeftParen(eachChar)){ //first item or left parenthesis
                    expressionStack.push(eachChar)
                }

                else if (isRightParen(eachChar)){
                    evaluateAndPushValueToStackUntilLeftParenthesis(valueStack, expressionStack)

                }

                //if the current operator has higher precedence than the first item in the stack, then it is fine.
                //Just insert the incoming
                else if (getHigherPrecedenceOperator(eachChar, expressionStack.peek())==eachChar){
                    expressionStack.push(eachChar)
                }

                //if the current operator is lesser, then the previous higher precedence expression have to be
                //evaluated. Else, we would be making wrong calculations while popping off for final evaluation
                else{

                    //the current operator has higher precedence. Evaluate expression
                    evaluateAndPushValueToValueStack(valueStack, expressionStack)

                    //after evaluation of the higher pair, don't forget to insert the current character into the expression stack
                    expressionStack.push(eachChar)


                }



            }
            else if (eachChar.isNumber()){
                eachNumber+=eachChar

                if (totalCharInInput==0){
                    valueStack.push(Long.parseLong(eachNumber)) //the last element
                }
            }

            /*else {
//other input (alphabets and special chars) are treated as garbage
}*/

            println ("Value Stack : "+valueStack)
            println ("Expression Stack : "+expressionStack)

        }

        println ("Final Expression stack " +expressionStack);
        println ("Final Value stack : "+valueStack)

        while (!expressionStack.empty){
            evaluateAndPushValueToValueStack(valueStack,expressionStack)
        }
        println ("Final value : "+valueStack)
    }

    boolean isRightParen(String operator) {
        operator==")"?true:false
    }

    boolean isLeftParen(String operator) {
        operator=="("?true:false
    }


    private void evaluateAndPushValueToValueStack(Stack<Long> valueStack, Stack<String> expressionStack) {

        Long firstOperand=valueStack.pop()
        Long secondOperand=valueStack.pop()
        println ("Value stack : "+firstOperand+ ":"+ secondOperand )
        Long evaluatedValue = this.evaluate(secondOperand, firstOperand, expressionStack.pop()) //intermediate result
        valueStack.push(evaluatedValue)
    }

    private void evaluateAndPushValueToStackUntilLeftParenthesis(Stack<Long> valueStack, Stack<String> expressionStack) {

        while (!expressionStack.empty){

            if (isLeftParen(expressionStack.peek())){ //if the left parenthesis has been reached, then pop it up and exit
                expressionStack.pop()
                break
            }

            evaluateAndPushValueToValueStack(valueStack,expressionStack)
        }

    }

    Long evaluate(Long firstOperand, Long secondOperand, String operator) {
        Long returnValue
        switch (operator) {
            case "+" :
                returnValue=firstOperand+secondOperand
                break
            case "-" :
                returnValue=firstOperand-secondOperand
                break;
            case "*":
                returnValue=firstOperand*secondOperand
                break
            case "/":

                if (secondOperand==0){ //cheating death by zero
                    returnValue=0
                }
                else{
                    returnValue=firstOperand/secondOperand
                }
                break;

        }

    }

    boolean isValidOperator(String input) {

        OPERATORS.contains(input)?true:false

    }

    String getHigherPrecedenceOperator(String firstOperator, String secondOperator){

        OPERATOR_LEVELS[firstOperator]<OPERATOR_LEVELS[secondOperator]?firstOperator:secondOperator

    }


}

 

 

 

Groovy (programming language)

Published at DZone with permission of Arun Manivannan, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • What Is Policy-as-Code? An Introduction to Open Policy Agent
  • Why It Is Important To Have an Ownership as a DevOps Engineer
  • The Role of Data Governance in Data Strategy: Part II
  • Select ChatGPT From SQL? You Bet!

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: