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 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.

Here is my implemention, I have fixed the while loop error:
#include
using namespace std;
#include
#include

bool IsOperator(char x) {
if (x == '+' || x == '-' || x == '*') {
return true;
}
return false;
}

bool IsOperand(char x) {
// cout<<"x"<<x<<endl;
if (x <= '9' && x >= '0') return true;
return false;

}

int PerformOperation(char c, int x, int y) {
if (c == '+') return(x + y);
else if (c == '-') return(x - y);
else if (c == '*') return(x * y);
else cout << "unexpected error" << endl;
return -1;
}

void Print(stack S) {
while (!S.empty()) {
cout << S.top() << endl;
S.pop();
}
cout << "" << endl;
}

int EvaluatePostfix(string expression) {
stack S;

for (int i = 0; i < expression.length(); i++) {
    // cout<<IsOperator(expression[i])<<endl;
   //  cout<<IsOperand(expression[i])<<endl;
    if (expression[i] == ' ' || expression[i] == ',') continue;
    else if (IsOperator(expression[i])) {
        int operand2 = S.top(); S.pop();
        if (S.empty()) { cout << "Error: check your postfix" << endl; return -1; }
        int operand1 = S.top(); S.pop();
        int result = PerformOperation(expression[i], operand1, operand2);
        S.push(result);
        cout << "进入operatorS is:" << endl;
        Print(S);
    }

    else if (IsOperand(expression[i])) {
        int operand = 0;
        while (IsOperand(expression[i]) && i < expression.length()) {
            operand = operand * 10 + (expression[i] - '0');
            i++;
            cout << i << endl;
        }
        i--;  //比如35 6+ 在遇到5后i++=2 在这次程序结束后还要自动+1 会跳过对i=2的判断  所以需要-1
        S.push(operand);
        cout << "进入operand S is:" << endl;
        Print(S);
    }


    //  cout << i << endl;
}
return S.top();

}

int main()
{
cout << "input postfix" << endl;
string expression;
// cin>>expression;
getline(cin, expression);
cout << "expression:" << expression << endl;
int result = EvaluatePostfix(expression);
cout << "result is " << result << endl;

}