PostfixEvaluation.cpp

/*
  Evaluation Of postfix Expression in C++ 
  Input Postfix expression must be in a desired format. 
  Operands must be integers and there should be space in between two operands.
  Only '+'  ,  '-'  , '*' and '/'  operators are expected. 
*/
#include<iostream>
#include<stack>
#include<string>

using namespace std;

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression);

// Function to perform an operation and return output. 
int PerformOperation(char operation, int operand1, int operand2);

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C);

// Function to verify whether a character is numeric digit. 
bool IsNumericDigit(char C);

int main() 
{
	string expression; 
	cout<<"Enter Postfix Expression \n";
	getline(cin,expression);
	int result = EvaluatePostfix(expression);
	cout<<"Output = "<<result<<"\n";
}

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression)
{
	// Declaring a Stack from Standard template library in C++. 
	stack<int> S;

	for(int i = 0;i< expression.length();i++) {

		// Scanning each character from left. 
		// If character is a delimitter, move on. 
		if(expression[i] == ' ' || expression[i] == ',') continue; 

		// If character is operator, pop two elements from stack, perform operation and push the result back. 
		else if(IsOperator(expression[i])) {
			// Pop two operands. 
			int operand2 = S.top(); S.pop();
			int operand1 = S.top(); S.pop();
			// Perform operation
			int result = PerformOperation(expression[i], operand1, operand2);
			//Push back result of operation on stack. 
			S.push(result);
		}
		else if(IsNumericDigit(expression[i])){
			// Extract the numeric operand from the string
			// Keep incrementing i as long as you are getting a numeric digit. 
			int operand = 0; 
			while(i<expression.length() && IsNumericDigit(expression[i])) {
				// For a number with more than one digits, as we are scanning from left to right. 
				// Everytime , we get a digit towards right, we can multiply current total in operand by 10 
				// and add the new digit. 
				operand = (operand*10) + (expression[i] - '0'); 
				i++;
			}
			// Finally, you will come out of while loop with i set to a non-numeric character or end of string
			// decrement i because it will be incremented in increment section of loop once again. 
			// We do not want to skip the non-numeric character by incrementing i twice. 
			i--;

			// Push operand on stack. 
			S.push(operand);
		}
	}
	// If expression is in correct format, Stack will finally have one element. This will be the output. 
	return S.top();
}

// Function to verify whether a character is numeric digit. 
bool IsNumericDigit(char C) 
{
	if(C >= '0' && C <= '9') return true;
	return false;
}

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C)
{
	if(C == '+' || C == '-' || C == '*' || C == '/')
		return true;

	return false;
}

// Function to perform an operation and return output. 
int PerformOperation(char operation, int operand1, int operand2)
{
	if(operation == '+') return operand1 +operand2;
	else if(operation == '-') return operand1 - operand2;
	else if(operation == '*') return operand1 * operand2;
	else if(operation == '/') return operand1 / operand2;

	else cout<<"Unexpected Error \n";
	return -1; 
}

why is he doing operand * 10
why cant he just do operand = (expression[i] - '0');
rather than operand = (operand*10) + (expression[i] - '0');

1

else if(IsNumericDigit(expression[i])){
  | // Extract the numeric operand from the string
  | // Keep incrementing i as long as you are getting a numeric digit.
  | int operand = 0;
  | while(i<expression.length() && IsNumericDigit(expression[i])) {
  | // For a number with more than one digits, as we are scanning from left to right.
  | // Everytime , we get a digit towards right, we can multiply current total in operand by 10
  | // and add the new digit.
  | operand = (operand*10) + (expression[i] - '0');
  | i++;
  | }
  | // Finally, you will come out of while loop with i set to a non-numeric character or end of string
  | // decrement i because it will be incremented in increment section of loop once again.
  | // We do not want to skip the non-numeric character by incrementing i twice.
  | i--;
  |  
  | // Push operand on stack.
  | S.push(operand);
  | }

i dint understand this part of the code .....pls explain me this part word by word
you have not mentioned this part in your you video so i dint understand....
and if possible can you please give me a c code for this????

@snehaagarwal625: the operand variable will store one - two digit number.
expression[i] - '0' is just a way to convert from char to int.

complete
last update
thanks

Complete Code in C
https://github.com/sid-fireskull/DataStructures-in-C/blob/master/postfix.c

@Mushi123
I just stopped by...
You can check an ASCII table for reference. The characters '0' through '9' match the decimal code of 48 to 57 correspondingly.
So if
char c1='2';
char c2='4';
Then c1 + c2 = 50 + 52 = 102

// check this out complete code in c

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#include<stdlib.h>
struct node
{
int data;
struct node* next;
};
struct node* top = NULL;
void push(int x)
{
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = x;
temp->next = top;
top = temp;
}
int pop()
{
int data;
struct node* temp = top;
if(top == NULL)
{
return -1;
}
temp = top;
data = top->data;
top = top->next;
free(temp);
return data;
}
bool isoperator(char x)
{
if(x=='+'||x=='-'||x==''||x=='/')
return true;
return false;
}
bool isnumericdigit(char x)
{
if(x>='0'&&x<='9')
return true;
return false;
}
int preop(char x,int operand1,int operand2)
{
if(x=='+')
return operand1+operand2;
else if(x=='-')
return operand1-operand2;
else if(x=='')
return operand1operand2;
else if(x=='/')
return operand1/operand2;
else
{
printf("invalid operator\n");
return -1;
}
}
int evalpostfix(char arr,int len)
{
int i;
for(i=0;i<len;i++)
{
if((arr+i)==' '||(arr+i)==',')
continue;
else if(isnumericdigit((arr+i)))
{
int operand = 0;
while(i<len && isnumericdigit((arr+i)))
{
operand = ((arr+i)-'0');
i++;
}
i--;
push(operand);
}
else if(isoperator((arr+i)))
{
int res;
int operand2 = pop();
int operand1 = pop();
res = preop(*(arr+i),operand1,operand2);
push(res);
}
}
return top->data;
}
int main()
{
char arr[20];
int res,length;
printf("enter the postfix expression: ");
gets(arr);
puts(arr);
length = strlen(arr);
printf("%d\n",length);
res = evalpostfix(arr,length);
printf("result = %d",res);
return 0;
}

why have you multiply operand with 10

why have you multiply operand with 10 @mehransaeed7810

bcse in program he used string to read every character so if we have 123 then 1st character is 1 and we would check whether it is integer or operator if it is integer then we have to multiply by 10 every time read all 1 ,2, 3 and then do that 1100+210+3*1, just check the problem based on reverse of number .

Hey does anybody has something simillar but with variables?
Like a =4; b= 7 then a+b or simillar?

Why -'0' in line 64

because it will typecast character to an integer type.

1

else if(IsNumericDigit(expression[i])){
  | // Extract the numeric operand from the string
  | // Keep incrementing i as long as you are getting a numeric digit.
  | int operand = 0;
  | while(i<expression.length() && IsNumericDigit(expression[i])) {
  | // For a number with more than one digits, as we are scanning from left to right.
  | // Everytime , we get a digit towards right, we can multiply current total in operand by 10
  | // and add the new digit.
  | operand = (operand*10) + (expression[i] - '0');
  | i++;
  | }
  | // Finally, you will come out of while loop with i set to a non-numeric character or end of string
  | // decrement i because it will be incremented in increment section of loop once again.
  | // We do not want to skip the non-numeric character by incrementing i twice.
  | i--;
  |  
  | // Push operand on stack.
  | S.push(operand);
  | }

i dint understand this part of the code .....pls explain me this part word by word
you have not mentioned this part in your you video so i dint understand....
and if possible can you please give me a c code for this????

actually it is write to check more than one digit number in our expression but its not working, here logic is incorrect, for loop and while loops never end so we will get segmentation fault..

Here is java code
`
import java.util.Scanner;
import java.util.Stack;

public class EvaluationPostfix {
static int operation(char operator,int op1,int op2){
switch(operator){
case '/':
return op1/op2;
case '':
return op1op2;
case '+':
return op1+op2;
case '-':
return op1-op2;
}
return 0;
}
static boolean isDigit(char c){
if('0' <= c && '9' >= c)
return true;
return false;
}
static int evaluate(String exp){
Stack st = new Stack<>();
char arr[] = exp.toCharArray();
int op1,op2;
for(int i=0;i<exp.length();i++){
if(arr[i] == ' ' || arr[i] == ',')
continue;
else if(arr[i] == '' || arr[i] == '/' || arr[i] == '+' || arr[i] == '-'){
op2=st.pop();
op1=st.pop();
st.push(operation(arr[i],op1,op2));
}else if(isDigit(arr[i])) {
int operand = 0;
while(i<exp.length() && isDigit(arr[i])){
operand = (operand10) + (arr[i]-'0');
i++;
}
i--;
st.push(operand);
}
}
return st.pop();
}

public static void main(String[] args) throws Exception {
    System.out.println("Insert PostFix expression");
    Scanner sc = new Scanner(System.in);
    String exp = sc.nextLine();
    sc.close();
    System.out.println("Answer is "+evaluate(exp));
}

}`

Java Prefix Evaluation code
import java.util.Scanner;
class PrefixEvaluation
{
String exp;
int []stack;
int top;
public PrefixEvaluation()
{
top=-1;
Scanner inp = new Scanner(System.in);
exp = inp.nextLine();
stack = new int[exp.length()];
}
public void push(int n)
{
stack[++top] = n;
}
public int pop()
{
return stack[top--];
}
public void evaluate()
{
for(int i=exp.length()-1;i>=0;i--)
{
char ch = exp.charAt(i);
if(ch == ' ')
{
// do nothing
}
else if(Character.isDigit(ch))
{
int temp_top=top;
int n=0;
while(Character.isDigit(ch))
{
n = (int)(ch - '0');
push(n);
i--;
ch = exp.charAt(i);
}
i++;
if(top!=temp_top)
{
n=0;
while(top!=temp_top)
{
n = n10 + pop();
}
push(n);
}
}
else
{
int result;
int val1 = pop();
int val2 = pop();
switch(ch)
{
case '+' :
result = val1 + val2;
push(result);
break;
case '' :
result = val1 * val2;
push(result);
break;
case '/' :
result = val1 / val2;
push(result);
break;
case '-' :
result = val1 - val2;
push(result);
break;
}
}
}
System.out.println("String length "+exp.length());
System.out.println("Top is at "+top);
System.out.println("Answer of the expression is "+stack[top]);
}
public static void main(String []args)
{
PrefixEvaluation ex = new PrefixEvaluation();
ex.evaluate();
}
}

Here is my implemetation for the same problem in C++

// Include all the required files
#include<iostream>
#include<stack>

// Define the namespace for standard library
using namespace std;

// Evaluates the result in the postfix expression.
int EvaluateResult(int operand1, int operand2, char symbol){
  if(symbol=='+') return operand1+operand2;       // Addition
  else if(symbol=='-') return operand1-operand2;  // Subtraction
  else if(symbol=='*') return operand1*operand2;  // Multiplication
  else if(symbol=='/') return operand1/operand2;  // Division
  else if(symbol=='%') return operand1%operand2;  // Modulus
  else if(symbol=='^') return operand1^operand2;  // Exponentiation
  else return -1;
}

// Evaluate PostFix expression using the stack algorithm methodology.
// Return -1 of invalid expression is given otherwise return the result.
int EvaluatePostfix(string expression){
  int i,num=-1;             // Variable declarations
  stack<int> temp_stack;

  for(i=0;i<expression.length();i++){ // Iterate over characters

    int mychar=expression[i];

    if(mychar==','){  // Delimiter comma handling
      if(num!=(-1)){
        temp_stack.push(num);
        num=-1;
      }
      continue;
    }else if(mychar-'0' <= 9 && mychar-'0' >= 0){  // Numbers handling 
      if(num==-1){
        num=mychar-'0'; // Find the exact number from the character
      }else{
        num=num*10+(mychar-'0');  // Number is greater than 1 digit.
      }
    }else if(mychar=='+'||mychar=='-'||mychar=='*'||mychar=='/'||mychar=='^'||mychar=='%'){  
      // Operating on the given symbols

      // Main Algorithm for the evaluation of result
      if(temp_stack.empty()) return -1;
      int operand2=temp_stack.top();
      temp_stack.pop();

      if(temp_stack.empty()) return -1;
      int operand1=temp_stack.top();
      temp_stack.pop();

      // Pop two previous elements from the stack and push their result onto stack again.
      temp_stack.push(EvaluateResult(operand1,operand2,mychar));
    }else{
      cout<<"Invalid operand";
    }
  }

  return temp_stack.top();
} // End of evaluation postfix

Include the main function as per your need. I have made a function to do the job :-)

Why do we need Linked List to store the data of Top element of the stack?

if(expression[i] == ' ' || expression[i] == ',') continue;
This line causing the error. So, I have to give input like "87-" with no space between and I can only use single-digit numbers. How to solve this Problem?

I have used comma as a delimiter. You can evaluate (87-) by giving the input as (8,7,-). I have done this because there could be both single and more than one digit numbers in the input. Suppose you want to evaluate 87 9 - then simply make the input as (87,9,-), that's it.

…

On Sat, Jun 13, 2020, 8:12 AM Nikhil Maheshwari ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ if(expression[i] == ' ' || expression[i] == ',') continue; This line causing the error. So, I have to give input like "87-" with no space between and I can only use single-digit numbers. How to solve this Problem? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <https://gist.github.com/7702441#gistcomment-3340133>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ALK4YY4TOZOGKAPEJ3E2IYLRWLRR7ANCNFSM4HMIARCA> .

Why -'0' in line 64

Because 0 in ASCII table is referred as 48 in decimal and 9 as 54 in decimal notation form.
Hence when evaluating the char to get integers this is very nice way of doing .

@arsharaj what function/work does this portion of your code do?
if(mychar==','){ // Delimiter comma handling
if(num!=(-1)){
temp_stack.push(num);
num=-1;
}
plzz can u explain?

The fact that '0' is 48, is it like a built in value? so if I write a program like:
char c1='2';
char c2='4';
then would c1+c2=6?

int x=c1+c2;
above expression will result in 102
so to get 6 do the following,
int x=c1+c2-2*'0';

evaluate expression to postfix() method 12 38 + 5 * with algorithm.
solution?

sir this code is not debuging

Don't forget to give the input in post fix form...

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int do_operation(int op2, int op1, char opr);
bool is_operator(char C);
bool is_operand(char C);

int evaluatePostfix(string exp) {
    stack<int> S;
    for(int i=0; i<exp.length(); i++) {
        if(exp[i] == ' ' || exp[i] ==',') {
            continue;
        }
        else if(is_operand(exp[i])) {
            int operand = 0;
            while(is_operand(exp[i])) {
                operand = operand*10 + exp[i] - '0' ;
                i++;
            }
            i--;
            S.push(operand);
        }

        else if(is_operator(exp[i])) {
            int op2 = S.top(); 
            S.pop();
            int op1 = S.top();
            S.pop();
            int result = do_operation(op2, op1, exp[i]);
            S.push(result);
        }
    }
    return S.top();
}

int do_operation(int op2, int op1, char opr) {
    if(opr == '/') return op1/op2;
    else if(opr == '*') return op1*op2;
    else if(opr == '+') return op1+op2;
    else if(opr == '-') return op1-op2;
    else {
        return -1;
    }
}

bool is_operator(char C) {
    if(C == '/' or '*' or '+' or '-') {
        return true;
    }
    else 
        return false;
}

bool is_operand(char C) {
    if(C>='0' && C<='9') {
        return true;
    }
    else 
        return false;
}

int main() {
    cout << evaluatePostfix("12 38 + 5 *"); // The input should be in postfix form
}

evaluate expression to postfix() method 12 38 + 5 * with algorithm.
solution?

@Malikhaidar

Why -'0' in line 64

Because of ASCII value , reference with 0

Hey can you leave the C code for it please?

#include<stdio.h>
#include<string.h>
#define MAX 30
struct stack
{
char str[MAX];
int top;
}s;

int checkoperand(char ch)
{
if(ch>='0' && ch<='9')
return 1;
return 0;
}

int operator(char ch)
{
if(ch=='*' || ch=='+' || ch=='/' || ch=='-')
return 1;
return 0;
}

void push(int data)
{
s.top++;
s.str[s.top]=data;
}

char peek()
{
return s.str[s.top];
}

void pop()
{
s.top--;
}

int operation(int x, int y, char op)
{
if(op == '+')
return y+x;
else if(op == '-')
return y-x;
else if(op == '')
return yx;
else if(op == '/')
return y/x;
else
return 0;
}

void evaluation()
{
int i,x,y;
char postfix[MAX];
printf("Enter postfix: ");
scanf("%s",&postfix);
for(i=0;i<strlen(postfix);)
{
if(checkoperand(postfix[i]))
push(postfix[i++]-'0');
else if(operator(postfix[i]))
{
x=peek();
pop();
y=peek();
pop();
push(operation(x,y,postfix[i]));
i++;
}
}
printf("%d",s.str[s.top]);
}

int main()
{
s.top=-1;
evaluation();
return 0;
}

I made minor changes in this code
It works fine now
Segementation error removed

/*
Evaluation Of postfix Expression in C++
Input Postfix expression must be in a desired format.
Operands must be single-digit integers and there should be space in between two operands.
Only '+' , '-' , '*' and '/' operators are expected.
*/

#include
#include
#include

using namespace std;

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression);

// Function to perform an operation and return output.
int PerformOperation(char operation, int operand1, int operand2);

// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C);

// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C);

int main()
{
string expression;
cout<<"Enter Postfix Expression \n";
getline(cin,expression);
int result = EvaluatePostfix(expression);
cout<<"Output = "<<result<<"\n";
}

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression)
{
// Declaring a Stack from Standard template library in C++.
stack S;

for(int i = 0;i< expression.length();i++) {

	// Scanning each character from left. 
	// If character is a delimitter, move on. 
	if(expression[i] == ' ' || expression[i] == ',') continue; 

	// If character is operator, pop two elements from stack, perform operation and push the result back. 
	else if(IsOperator(expression[i])) {
		// Pop two operands. 
		int operand2 = S.top(); S.pop();
		int operand1 = S.top(); S.pop();
		// Perform operation
		int result = PerformOperation(expression[i], operand1, operand2);
		//Push back result of operation on stack. 
		S.push(result);
	}


           else if(IsNumericDigit(expression[i])) {		    
                    int operand;		    
                    operand = expression[i] - '0';	
			
                   // Push operand on stack. 			
                   S.push(operand);		
             }

}
// If expression is in correct format, Stack will finally have one element. This will be the output. 
return S.top();

}

// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C)
{
if(C >= '0' && C <= '9') return true;
return false;
}

// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C)
{
if(C == '+' || C == '-' || C == '*' || C == '/')
return true;

return false;

}

// Function to perform an operation and return output.
int PerformOperation(char operation, int operand1, int operand2)
{
if(operation == '+') return operand1 +operand2;
else if(operation == '-') return operand1 - operand2;
else if(operation == '*') return operand1 * operand2;
else if(operation == '/') return operand1 / operand2;

else cout<<"Unexpected Error \n";
return -1; 

}

// here we are only considering single-digit integers, because if we start considering integers > 9 then 2 single-digit integer might get interpreted as 1 two-digit integer and we will get segmentaion error (because PerformOperation function is expecting two integers in stack whereas only 1 is found)

Why -'0' in line 64
为了把字符转换成数字

char in C++ evaluates to the decimal equivalent.
'0' is 48
'1' is 49
'2' is 50
.
.
.
if expression[i] = '2' which evaluates to 50
so (expression[i] - '0') in this case will be (50 - 48) = 2

The reason segmentation fault happens is that you don't put space between each operand.
For example, if you type: "11+", it's buggy. It must be "1 1+" or "1 1 +".
By applying this logic, it can count up multi digits numbers.