Postfix evaluation for multi-digit numbers

The above program can be extended for multiple digits by adding a separator-like space between all elements (operators and operands) of the given expression.

Below given is the extended program which allows operands to have multiple digits.

C

// C program to evaluate value of a postfix
// expression having multiple digit operands
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// Stack type
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};
 
// Stack Operations
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack
        = (struct Stack*)malloc(sizeof(struct Stack));
 
    if (!stack)
        return NULL;
 
    stack->top = -1;
    stack->capacity = capacity;
    stack->array
        = (int*)malloc(stack->capacity * sizeof(int));
 
    if (!stack->array)
        return NULL;
 
    return stack;
}
 
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
 
int peek(struct Stack* stack)
{
    return stack->array[stack->top];
}
 
int pop(struct Stack* stack)
{
    if (!isEmpty(stack))
        return stack->array[stack->top--];
    return '$';
}
 
void push(struct Stack* stack, int op)
{
    stack->array[++stack->top] = op;
}
 
// The main function that returns value
// of a given postfix expression
int evaluatePostfix(char* exp)
{
    // Create a stack of capacity equal to expression size
    struct Stack* stack = createStack(strlen(exp));
    int i;
 
    // See if stack was created successfully
    if (!stack)
        return -1;
 
    // Scan all characters one by one
    for (i = 0; exp[i]; ++i) {
        // if the character is blank space then continue
        if (exp[i] == ' ')
            continue;
 
        // If the scanned character is an
        // operand (number here),extract the full number
        // Push it to the stack.
        else if (isdigit(exp[i])) {
            int num = 0;
 
            // extract full number
            while (isdigit(exp[i])) {
                num = num * 10 + (int)(exp[i] - '0');
                i++;
            }
            i--;
 
            // push the element in the stack
            push(stack, num);
        }
 
        // If the scanned character is an operator, pop two
        // elements from stack apply the operator
        else {
            int val1 = pop(stack);
            int val2 = pop(stack);
 
            switch (exp[i]) {
            case '+':
                push(stack, val2 + val1);
                break;
            case '-':
                push(stack, val2 - val1);
                break;
            case '*':
                push(stack, val2 * val1);
                break;
            case '/':
                push(stack, val2 / val1);
                break;
            }
        }
    }
    return pop(stack);
}
 
// Driver program to test above functions
int main()
{
    char exp[] = "100 200 + 2 / 5 * 7 +";
   
    // Function call
    printf("%d", evaluatePostfix(exp));
    return 0;
}
 
// This code is contributed by Arnab Kundu

C++14

// C++ program to evaluate value of a postfix
// expression having multiple digit operands
#include <bits/stdc++.h>
using namespace std;
 
// The main function that returns value
// of a given postfix expression
int evaluatePostfix(char* exp)
{
    // Create a stack of capacity equal to expression size
    stack<int> st;
    int i;
 
    // Scan all characters one by one
    for (i = 0; exp[i]; ++i) {
         
        // If the character is blank space then continue
        if (exp[i] == ' ')
            continue;
 
        // If the scanned character is an
        // operand (number here),extract the full number
        // Push it to the stack.
        else if (isdigit(exp[i])) {
            int num = 0;
 
            // Extract full number
            while (isdigit(exp[i])) {
                num = num * 10 + (int)(exp[i] - '0');
                i++;
            }
            i--;
 
            // Push the element in the stack
            st.push(num);
        }
 
        // If the scanned character is an operator, pop two
        // elements from stack apply the operator
        else {
            int val1 = st.top();
            st.pop();
            int val2 = st.top();
            st.pop();
 
            switch (exp[i]) {
            case '+':
                st.push(val2 + val1);
                break;
            case '-':
                st.push(val2 - val1);
                break;
            case '*':
                st.push(val2 * val1);
                break;
            case '/':
                st.push(val2 / val1);
                break;
            }
        }
    }
    return st.top();
}
 
// Driver code
int main()
{
    char exp[] = "100 200 + 2 / 5 * 7 +";
   
    // Function call
    cout << evaluatePostfix(exp);
    return 0;
}
 
// This code is contributed by rathbhupendra

Java

// Java program to evaluate value of a postfix
// expression having multiple digit operands
import java.util.Stack;
 
class Test1 {
     
    // Method to evaluate value of a postfix expression
    static int evaluatePostfix(String exp)
    {
        // Create a stack
        Stack<Integer> stack = new Stack<>();
 
        // Scan all characters one by one
        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);
 
            if (c == ' ')
                continue;
 
            // If the scanned character is an operand
            // (number here),extract the number
            // Push it to the stack.
            else if (Character.isDigit(c)) {
                int n = 0;
 
                // Extract the characters and store it in num
                while (Character.isDigit(c)) {
                    n = n * 10 + (int)(c - '0');
                    i++;
                    c = exp.charAt(i);
                }
                i--;
 
                // Push the number in stack
                stack.push(n);
            }
 
            // If the scanned character is an operator, pop
            // two elements from stack apply the operator
            else {
                int val1 = stack.pop();
                int val2 = stack.pop();
 
                switch (c) {
                case '+':
                    stack.push(val2 + val1);
                    break;
                case '-':
                    stack.push(val2 - val1);
                    break;
                case '/':
                    stack.push(val2 / val1);
                    break;
                case '*':
                    stack.push(val2 * val1);
                    break;
                }
            }
        }
        return stack.pop();
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        String exp = "100 200 + 2 / 5 * 7 +";
       
        // Function call
        System.out.println(evaluatePostfix(exp));
    }
}
 
// This code is contributed by Arnab Kundu

Python3

# Python program to evaluate value of a postfix
# expression with integers containing multiple digits
 
 
class evalpostfix:
    def __init__(self):
        self.stack = []
        self.top = -1
 
    def pop(self):
        if self.top == -1:
            return
        else:
            self.top -= 1
            return self.stack.pop()
 
    def push(self, i):
        self.top += 1
        self.stack.append(i)
 
    def centralfunc(self, ab):
        for i in ab:
 
            # If the component of the list is an integer
            try:
                self.push(int(i))
             
            # If the component of the list is not an integer,
            # it must be an operator. Using ValueError, we can
            # evaluate components of the list other than type int
            except ValueError:
                val1 = self.pop()
                val2 = self.pop()
                if i == '/':
                    self.push(val2 / val1)
                else:
                     
                    # Switch statement to perform operation
                    switcher = {'+': val2 + val1, '-': val2 -
                                val1, '*': val2 * val1, '^': val2**val1}
                    self.push(switcher.get(i))
        return int(self.pop())
 
 
 
# Driver code
if __name__ == '__main__':
    str = '100 200 + 2 / 5 * 7 +'
     
    # Splitting the given string to obtain
    # integers and operators into a list
    strconv = str.split(' ')
    obj = evalpostfix()
    print(obj.centralfunc(strconv))
 
# This code is contributed by Amarnath Reddy

C#

// C# program to evaluate value of a postfix
// expression having multiple digit operands
using System;
using System.Collections.Generic;
 
class GFG {
     
    // Method to evaluate value of
    // a postfix expression
    public static int evaluatePostfix(string exp)
    {
        // Create a stack
        Stack<int> stack = new Stack<int>();
 
        // Scan all characters one by one
        for (int i = 0; i < exp.Length; i++) {
            char c = exp[i];
 
            if (c == ' ') {
                continue;
            }
 
            // If the scanned character is an
            // operand (number here),extract
            // the number. Push it to the stack.
            else if (char.IsDigit(c)) {
                int n = 0;
 
                // Extract the characters and
                // store it in num
                while (char.IsDigit(c)) {
                    n = n * 10 + (int)(c - '0');
                    i++;
                    c = exp[i];
                }
                i--;
 
                // push the number in stack
                stack.Push(n);
            }
 
            // If the scanned character is
            // an operator, pop two elements
            // from stack apply the operator
            else {
                int val1 = stack.Pop();
                int val2 = stack.Pop();
 
                switch (c) {
                case '+':
                    stack.Push(val2 + val1);
                    break;
 
                case '-':
                    stack.Push(val2 - val1);
                    break;
 
                case '/':
                    stack.Push(val2 / val1);
                    break;
 
                case '*':
                    stack.Push(val2 * val1);
                    break;
                }
            }
        }
        return stack.Pop();
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        string exp = "100 200 + 2 / 5 * 7 +";
       
        // Function call
        Console.WriteLine(evaluatePostfix(exp));
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
    // Javascript program to evaluate value of a postfix
    // expression having multiple digit operands
     
    // Method to evaluate value of
    // a postfix expression
    function evaluatePostfix(exp)
    {
        // create a stack
        let stack = [];
 
        // Scan all characters one by one
        for (let i = 0; i < exp.length; i++)
        {
            let c = exp[i];
 
            if (c == ' ')
            {
                continue;
            }
 
            // If the scanned character is an 
            // operand (number here),extract
            // the number. Push it to the stack.
            else if (c >= '0' && c <= '9')
            {
                let n = 0;
 
                // extract the characters and
                // store it in num
                while (c >= '0' && c <= '9')
                {
                    n = n * 10 + (c - '0');
                    i++;
                    c = exp[i];
                }
                i--;
 
                // push the number in stack
                stack.push(n);
            }
 
            // If the scanned character is
            // an operator, pop two elements
            // from stack apply the operator
            else
            {
                let val1 = stack.pop();
                let val2 = stack.pop();
 
                switch (c)
                {
                    case '+':
                    stack.push(val2 + val1);
                    break;
 
                    case '-':
                    stack.push(val2 - val1);
                    break;
 
                    case '/':
                    stack.push(parseInt(val2 / val1, 10));
                    break;
 
                    case '*':
                    stack.push(val2 * val1);
                    break;
                }
            }
        }
        return stack.pop();
    }
     
    let exp = "100 200 + 2 / 5 * 7 +";
    document.write(evaluatePostfix(exp));
 
// This code is contributed by decode2207.
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Postfix evaluation for multi-digit numbers

C

C++14

Java

Python3

C#

Javascript

Evaluation of Postfix Expression

Similar Reads