BlogsDope image BlogsDope

Expression Parsing: Part 2

July 23, 2020 C JAVA C++ PYTHON ALGORITHM 7178

For evaluating an arithmetic expression, we need to convert it into prefix or postfix notation. I have talked about it in this post. Here also we will use a stack data structure to evaluate prefix and postfix expressions.

Evaluation of Postfix Expression


Input: 3 6 4 + * 5 /
Output: 6

Algorithm to evaluate postfix expression

  1. Scan the postfix expression from left to right.
  2. If the scanned character is an operand, then push it to the stack.
  3. Else if the scanned character is an operator, pop two operands from the top of the stack and evaluate them with the scanned operator and push the result into the stack. (Note: here evaluation should be second_pop_operand operator first_pop_operand.)
  4. Repeat steps 2 and 3 until all the characters in the postfix expression are scanned.
  5. Print the final result from the top of the stack.

Step by step evaluation of postfix expression “3 6 4 + * 5 /” is shown below in the table,

Steps

Scanned Character

Stack

Action

Initially

 

[Empty Stack]

 

1

3

3

Push 3

2

6

3,6

Push 6

3

4

3,6,4

Push 4

4

+

3,10

Pop 4, Pop 6 and Push 6+4 = 10

5

*

30

Pop 10, Pop 3 and Push 3*10= 30

6

5

30,5

Push 5

7

/

6

Pop 5, Pop 30 and Push 30/5 = 6

Final Result:-

6

  • C/C++
  • Python
  • Java
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
// Check if a character is operator or not.
int operators(char ch)
{
    if (ch == '^' || ch == '/' || ch == '*' || ch == '+' || ch == '-' || ch == '(')
    {
        return 1;
    }
    return 0;
}
int evaluate(char op, int e1, int e2)
{
    switch (op)
    {
    case '^':
        return pow(e1, e2);
    case '*':
        return e1 * e2;
    case '/':
        return e1 / e2;
    case '+':
        return e1 + e2;
    case '-':
        return e1 - e2;
    }
    return 0;
}
int evalPostfix(string expression)
{
    stack<int> Stack;
    istringstream stm(expression);
    string expr;
    while (stm >> expr)
    {
        if (operators(expr[0]))
        {
            int a = Stack.top();
            Stack.pop();
            int b = Stack.top();
            Stack.pop();
            int res = evaluate(expr[0], b, a);
            Stack.push(res);
        }
        else
            Stack.push(stoi(expr));
    }
    return Stack.top();
}
int main()
{
    string expr = "3 6 4 + * 5 /";
    cout << "Postfix: " << expr << endl;
    cout << "Result: " << evalPostfix(expr);
}
import operator

operators = {
    "^": operator.pow,
    "*": operator.mul,
    "/": operator.truediv,
    "+": operator.add,
    "-": operator.sub,
}


def evalPostfix(expression):
    op = expression.split(" ")
    stack = []
    for exp in op:
        # If operator pop two operands, evaluate them
        #   and push result to stack.
        if exp in ["^", "*", "/", "+", "-"]:
            a = stack.pop()
            b = stack.pop()
            res = operators[exp](int(b), int(a))
            stack.append(res)
        # if operand push to stack.
        else:
            stack.append(exp)
    return stack.pop()


if __name__ == "__main__":
    exp = "3 6 4 + * 5 /"
    print(f"Postfix: {exp}")
    print(f"Result: {evalPostfix(exp)}")
import java.util.*;

public class MyClass {
  public static void main(String args[]) {
    String exp = "3 6 4 + * 5 /";
    System.out.println("Postfix: " + exp);
    System.out.println("Result: " + evalPostfix(exp));
  }

  public static int evaluate(String op, int e1, int e2) {
    switch (op) {
      case "^":
        return (int) Math.pow(e1, e2);
      case "*":
        return e1 * e2;
      case "/":
        return e1 / e2;
      case "+":
        return e1 + e2;
      case "-":
        return e1 - e2;
    }
    return 0;
  }

  // Check if a character is operator or not.
  public static boolean operator(String ch) {
    if ("^".equals(ch) || "/".equals(ch) || "*".equals(ch) || "+".equals(ch) || "-".equals(ch))
      return true;
    return false;
  }

  static int evalPostfix(String expression) {
    String op[] = expression.split(" ");
    Stack<String> stack = new Stack();
    for (String exp : op) {
      // If operator pop two operands, evaluate them
      // and push result to stack.
      if (operator(exp)) {
        int a = Integer.parseInt(stack.pop());
        int b = Integer.parseInt(stack.pop());
        int res = evaluate(exp, b, a);
        stack.push(Integer.toString(res));
      }
      // if operand push to stack.
      else
        stack.push(exp);
    }
    return Integer.parseInt(stack.pop());
  }
}

Evaluation of Prefix expression


Input: * 3 / + 6 4 5
Output: 6

Algorithm to Evaluate Prefix Expression


Steps to evaluate prefix expression is same as evaluation of postfix expression with one additional step i.e. step 1.

  1. Reverse the prefix expression.
  2. Scan the reversed prefix expression from left to right.
  3. If the scanned character is an operand, then push it to the stack.
  4. Else if the scanned character is an operator, pop two operands from the top of the stack and evaluate them with the scanned operator and push the result into the stack. (Note: here evaluation should be first_pop_operand operator second_pop_operand.)
  5. Repeat steps 2 and 3 until all the characters in reversed prefix expression are scanned.
  6. Print the final result from the top of the stack.

Step by step evaluation of prefix expression “* 3 / + 6 4 5” is shown below in the table. In step 1, the prefix expression is reversed and hence the new expression becomes “5 4 6 + / 3 *”.

Steps

Scanned Character

Stack

Action

Initially

 

[Empty Stack]

 

1

5

5

Push 5

2

4

5,4

Push 4

3

6

5,4,6

Push 6

4

+

5,10

Pop 6, Pop 4 and Push 6+4 = 10

5

/

2

Pop 10, Pop 5 and Push 10/5 = 30

6

3

2,3

Push 3

7

*

6

Pop 3, Pop 2 and Push 3*2 = 6

Final Result:-

6

  • C/C++
  • Python
  • Java
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
// Check if a character is operator or not.
int operators(char ch)
{
    if (ch == '^' || ch == '/' || ch == '*' || ch == '+' || ch == '-' || ch == '(')
    {
        return 1;
    }
    return 0;
}
int evaluate(char op, int e1, int e2)
{
    switch (op)
    {
    case '^':
        return pow(e1, e2);
    case '*':
        return e1 * e2;
    case '/':
        return e1 / e2;
    case '+':
        return e1 + e2;
    case '-':
        return e1 - e2;
    }
    return 0;
}
int evalPostfix(string expression)
{
    reverse(expression.begin(), expression.end());
    stack<int> Stack;
    istringstream stm(expression);
    string expr;
    while (stm >> expr)
    {
        if (operators(expr[0]))
        {
            int a = Stack.top();
            Stack.pop();
            int b = Stack.top();
            Stack.pop();
            int res = evaluate(expr[0], a, b);
            Stack.push(res);
        }
        else
            Stack.push(stoi(expr));
    }
    return Stack.top();
}
int main()
{
    string expr = "* 3 / + 6 4 5";
    cout << "Postfix: " << expr << endl;
    cout << "Result: " << evalPostfix(expr);
}
import operator

operators = {
    "^": operator.pow,
    "*": operator.mul,
    "/": operator.truediv,
    "+": operator.add,
    "-": operator.sub,
}


def evalPrefix(expression):
    op = expression[::-1].split(" ")
    stack = []
    for exp in op:
        # If operator pop two operands, evaluate them
        #   and push result to stack.
        if exp in ["^", "*", "/", "+", "-"]:
            a = stack.pop()
            b = stack.pop()
            res = operators[exp](int(a), int(b))
            stack.append(res)
        # if operand push to stack.
        else:
            stack.append(exp)
    return stack.pop()


if __name__ == "__main__":
    exp = "* 3 / + 6 4 5"
    print(f"Prefix: {exp}")
    print(f"Result: {evalPrefix(exp)}")
import java.util.*;

public class MyClass {
  public static void main(String args[]) {
    String exp = "* 3 / + 6 4 5";
    System.out.println("Prefix: " + exp);
    System.out.println("Result: " + evalPrefix(exp));
  }

  public static int evaluate(String op, int e1, int e2) {
    switch (op) {
      case "^":
        return (int) Math.pow(e1, e2);
      case "*":
        return e1 * e2;
      case "/":
        return e1 / e2;
      case "+":
        return e1 + e2;
      case "-":
        return e1 - e2;
    }
    return 0;
  }

  // Check if a character is operator or not.
  public static boolean operator(String ch) {
    if ("^".equals(ch) || "/".equals(ch) || "*".equals(ch) || "+".equals(ch) || "-".equals(ch))
      return true;
    return false;
  }

  static int evalPrefix(String expression) {
    String op[] = expression.split(" ");
    Stack<String> stack = new Stack();
    for (int i = op.length - 1; i >= 0; i--) {
      String exp = op[i];
      // If operator pop two operands, evaluate them
      // and push result to stack.
      if (operator(exp)) {
        int a = Integer.parseInt(stack.pop());
        int b = Integer.parseInt(stack.pop());
        int res = evaluate(exp, a, b);
        stack.push(Integer.toString(res));
      }
      // if operand push to stack.
      else
        stack.push(exp);
    }
    return Integer.parseInt(stack.pop());
  }
}

Liked the post?
Editor's Picks
0 COMMENT

Please login to view or add comment(s).