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; 
}

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.