Conversion of infix string to postfix and evaluation of postfix string to make a simple calculator application in C++.
(A) Algorithm for converting an infix expression into postfix operation
1. Add “(“ at the beginning and “)” at the end of an infix expression Q.
2. Scan Q from left to right and repeat step 3 to step 6.
3 If an operand is encountered, add it into postfix P.
4. If a left parenthesis is encountered, push it onto the stack S
5. If and operator op is encountered then,
(a) Repeatedly pop from stack S and add it to postfix each operator which has
same precedence as or higher precedence than op.
(b) Add op to Stack S.
6. If a right parenthesis is encountered, then
(a) Repeatedly pop from stack S and add
it to postfix each operator until a left parenthesis is encountered on stacks.
(b) Remove the left parenthesis.
2. Scan Q from left to right and repeat step 3 to step 6.
3 If an operand is encountered, add it into postfix P.
4. If a left parenthesis is encountered, push it onto the stack S
5. If and operator op is encountered then,
(a) Repeatedly pop from stack S and add it to postfix each operator which has
same precedence as or higher precedence than op.
(b) Add op to Stack S.
6. If a right parenthesis is encountered, then
(a) Repeatedly pop from stack S and add
it to postfix each operator until a left parenthesis is encountered on stacks.
(b) Remove the left parenthesis.
(B) Algorithm for evaluation of postfix string
1. Scan postfix P from left to right and repeat step 2 and 3 for each element of P until the
NULL character or other symbol is encountered.
2. If an operand is encountered then push it on to the stack.
3. If an operator op is encountered, then
(a) Remove the top elements of stack S where A is the
top element and B is next top element
(b) Evaluate B op A
(c) Place the result back onto the stack S
(d) Return top of the stack which is required
the result of our calculation
NULL character or other symbol is encountered.
2. If an operand is encountered then push it on to the stack.
3. If an operator op is encountered, then
(a) Remove the top elements of stack S where A is the
top element and B is next top element
(b) Evaluate B op A
(c) Place the result back onto the stack S
(d) Return top of the stack which is required
the result of our calculation
Source code for both infix to postfix and postfix evaluation
The code is also available on GitHub.
Program: Conversion of Infix to Postfix String and Evaluation
Language: C/C++
by Bibek Subedi
June 13, 2011
Operators Used
1. '+' For addition
2. '-' For Subtraction
3. '*' For Multiplication
4. '/' For Division
5. '^' For Exponentiation
Program Limitations
* This program Only process single digit operations
* Can't handle unary operation
* Only process left to right associativity
***************************************************/
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <string>
#define MAX_SIZE 20
using namespace std;
template <class T>
class Stack {
private:
T item[MAX_SIZE];
int top;
public:
Stack()
{
top = -1;
}
void push(T data)
{
if (!this->is_full())
item[++top] = data;
else {
cout << "Stack Error" << endl;
exit(10);
}
}
T pop()
{
if (!this->is_empty())
return item[top--];
else {
cout << "Stack is Empty" << endl;
exit(11);
}
}
int size()
{
return top + 1;
}
bool is_empty()
{
if (top == -1)
return true;
else
return false;
}
bool is_full()
{
if (top == MAX_SIZE - 1)
return true;
else
return false;
}
void display()
{
for (int i = 0; i < this->size(); i++) {
cout << item[i] << " ";
}
cout << endl;
}
T return_top()
{
return item[top];
}
};
class Convert {
private:
bool num_flag;
bool two_digit_flag;
public:
Convert();
string return_with_bracket(string infix);
void to_Postfix(string infix, char postfix[]);
bool prcd(char op1, char op2);
int isOperand(char op);
int isOperator(char op);
bool return_flag()
{
return num_flag;
}
};
Convert::Convert()
{
this->num_flag = false;
this->two_digit_flag = false;
}
string Convert::return_with_bracket(string infix)
{
return ("(" + infix + ")");
}
bool Convert::prcd(char op1, char op2)
{
if ((op1 == '+' || op1 == '-' || op1 == '*' || op1 == '/') && op2 == '(')
return true;
if (op1 == '+' && op2 == '+')
return true;
if (op1 == '-' && op2 == '-')
return false;
if (op1 == '-' && op2 == '+')
return false;
if (op1 == '+' && op2 == '-')
return false;
if (op1 == '/' && op2 == '/')
return false;
if (op1 == '/' && (op2 == '-' || op2 == '+'))
return true;
if (op1 == '*' && (op2 == '+' || op2 == '-'))
return true;
if ((op1 == '-' || op1 == '+') && (op2 == '*' || op2 == '/'))
return false;
if ((op1 == '$' || op1 == '+') && (op2 == '*' || op2 == '/' || op2 == '-'))
return true;
if ((op1 == '-' || op1 == '+' || op1 == '*' || op1 == '/') && op2 == '^')
return false;
if (op1 == '^' && (op2 == '+' || op2 == '*' || op2 == '/' || op2 == '-'))
return false;
}
int Convert::isOperand(char op)
{
return (op >= '0' && op <= '9');
}
int Convert::isOperator(char op)
{
return (op == '+' || op == '-' || op == '/' || op == '*' || op == '^');
}
void Convert::to_Postfix(string infix, char postfix[])
{
int position, outpos = 0;
char c;
int count = 0;
char temp;
char stacktop;
Stack<char> stack;
for (position = 0; (c = infix[position]) != '\0'; position++) {
if (this->isOperand(c)) {
postfix[outpos++] = c;
this->num_flag = true;
count++;
if (count >= 2) {
this->two_digit_flag = true;
}
}
else if (this->isOperator(c)) {
count = 0;
if (isOperator(infix[position]) && isOperator(infix[position + 1])) {
cout << "\aMissing argument in between " << infix[position] << " and " << infix[position + 1]
<< " in column " << position + 1 << endl;
exit(9);
}
if (this->prcd(c, stacktop)) {
stacktop = stack.return_top();
stack.push(c);
stacktop = c;
}
else {
while (true) {
temp = stack.pop();
postfix[outpos++] = temp;
stacktop = stack.return_top();
if (prcd(c, stacktop) || stacktop == '(')
break;
}
stack.push(c);
stacktop = stack.return_top();
}
}
else if (c == '(') {
count = 0;
stack.push(c);
stacktop = stack.return_top();
}
else if (c == ')') {
count = 0;
while (1) {
if (stack.size() == 0) {
cout << "Warning!! Number of ')' is greater than '('" << endl;
exit(2);
}
temp = stack.pop();
if (temp != '(') {
postfix[outpos++] = temp;
}
else {
break;
}
}
stacktop = stack.return_top();
}
else {
cout << "Invalid input";
exit(3);
}
if (infix[position] == ')' && infix[position + 1] == '(') {
stack.push('*');
stacktop = stack.return_top();
}
}
if (stack.size() != 0) {
cout << "Warning!!Number of '(' is greater than ')'" << endl;
// exit(6);
}
if (!this->return_flag()) {
cout << "You must Enter Numeric value for calculation" << endl;
cout << "This program cannot perform operations on variables";
exit(5);
}
if (this->two_digit_flag) {
cout << "Sory! Althoug u may have entered right string" << endl;
cout << "this program is only for single digit operation" << endl;
exit(8);
}
postfix[outpos] = '\0';
}
class Evaluate {
public:
double eval(char expr[], Convert&);
double oper(int symb, double op1, double op2);
};
double Evaluate::oper(int symb, double op1, double op2)
{
switch (symb) {
case '+':
return (op1 + op2);
case '-':
return (op1 - op2);
case '*':
return (op1 * op2);
case '/':
return (op1 / op2);
case '^':
return (pow(op1, op2));
}
}
double Evaluate::eval(char expr[], Convert& convert)
{
int c, position;
char temp1;
int count = 0;
double opnd1, opnd2, value;
Stack<double> stack;
for (position = 0; (c = expr[position]) != '\0'; position++) {
if (convert.isOperand(c)) {
temp1 = double(c - '0');
stack.push(temp1);
}
else {
opnd2 = stack.pop();
if (stack.size() == 0) {
cout << "This program cannot process unary operation";
exit(1);
}
opnd1 = stack.pop();
value = oper(c, opnd1, opnd2);
stack.push(value);
}
}
if (stack.size() >= 2) {
cout << "Sory! this program cannot calculate this" << endl;
cout << "Enter +, *, /, - or ^ between bracket" << endl;
exit(4);
}
return (stack.pop());
}
int main()
{
Convert convert;
Evaluate evaluate;
string bracketted_infix;
char infix[50], postfix[50];
char choice;
while (1) {
cout << "Enter string: ";
cin >> infix;
cout << endl;
cout << "Entered String: " << infix << endl;
bracketted_infix = convert.return_with_bracket(infix);
convert.to_Postfix(bracketted_infix, postfix);
cout << "Equivalent Postfix string: " << postfix << endl;
cout << "RESULT: ";
cout << evaluate.eval(postfix, convert);
cout << "\nCalculate another string?(y/n) ";
cin >> choice;
cout << endl;
if (choice == 'n')
break;
}
return 0;
}
How would you implement sin() and cos() functions? and variables like x and y, something like z=2x*sin(4y)
It is a very simple conversion from infix to postfix which is valid for simple algebraic calculation and only for single digit. To perform such type of calculation you need parsing and other difficult algorithm. See the limitation that I have written in the source file
Hi again, I was wondering if you could explain me some things,could you explain, what does the "bool Convert::prcd(char op1, char op2){" function do? I kinda have the idea that it chooses which operator to use and the put it into a stack, but I'm not sure of how exactly it works, and if you could please tell me in witch part do you change the char of an operand to an actual number to evaluate? I know that it might be in the "double Evaluate::eval(char expr[],Convert &convert){" function, but I was expecting to see an "atoi" or an "atof" to convert the chars. I hope you don't mind answer me, I pretty green at C++
Hi Raven609, thank u for re visiting my blog. The function prcd ( char op1, char op2) checks the precedence of operators. It returns true if operator op1 has higher precedence than operator op2 otherwise returns false. The code c – '0' converts the character into number i.e integer (why ?) . When you try to subtract character '0' from character c, the compiler converts both character into corresponding ASCII values and returns the result. Try subtracting '1' – '0' and '1' – 0 then you will understand the concept.
Step 5 is confusing
Step 5 from algorithm (A)
Step 6 is for balancing opening and closing brackets. It removes the popped left bracket.