C++ Infix to Postfix and Evaluating postfix. Write a C++ program that will take
ID: 3681144 • Letter: C
Question
C++ Infix to Postfix and Evaluating postfix. Write a C++ program that will take any input Infix computation consisting of (, ), +, -, *, / and positive numeric operands and convert it to postfix. Use a stack to do this program. Secondly, use the postfix form of the computation to actually calculate the result of applying the operators to the operands. In other words, use the output of the first part (a postfix string) to calculate the result. The precedence order is as follows: •* / = operators which have same precedence •+ - = operators which have same precedence •) = lower precedence than the operators •( = lowest precedence The computation should be input as a single string. Assume it is always correct with regard to format and parenthesis balancing, so erros don't need to addressed. After converting the expression from infix to postfix, the output must have an evaluated/calculated form as the final answer.
Explanation / Answer
working c++ code for the same compiled on ideone:
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
struct node
{
int data;
node *next;
}*p = NULL, *top = NULL, *save = NULL, *ptr;
void mypush(int x)
{
p = new node;
p->data = x;
p->next = NULL;
if (top == NULL)
{
top = p;
}
else
{
save = top;
top = p;
p->next = save;
}
}
char mypop()
{
if (top == NULL)
{
cout<<"underflow!!";
}
else
{
ptr = top;
top = top->next;
return(ptr->data);
delete ptr;
}
}
int getWeight(char ch) {
switch (ch) {
case '/':
case '*': return 2;
case '+':
case '-': return 1;
default : return 0;
}
}
void infix2postfix(char infix[], char postfix[], int size) {
stack<char> s;
int weight;
int i = 0;
int k = 0;
char ch;
while (i < size) {
ch = infix[i];
if (ch == '(') {
s.push(ch);
i++;
continue;
}
if (ch == ')') {
while (!s.empty() && s.top() != '(') {
postfix[k++] = s.top();
s.pop();
}
if (!s.empty()) {
s.pop();
}
i++;
continue;
}
weight = getWeight(ch);
if (weight == 0) {
postfix[k++] = ch;
}
else {
if (s.empty()) {
s.push(ch);
}
else {
while (!s.empty() && s.top() != '(' &&
weight <= getWeight(s.top())) {
postfix[k++] = s.top();
s.pop();
}
s.push(ch);
}
}
i++;
}
while (!s.empty()) {
postfix[k++] = s.top();
s.pop();
}
postfix[k] = 0;
}
int main() {
int a,b;
char infix[] = "1*2+6/2";
int size = strlen(infix);
char postfix[size];
infix2postfix(infix,postfix,size);
cout<<" Infix Expression :: "<<infix;
cout<<" Postfix Expression :: "<<postfix;
for (int i = 0; i < strlen(postfix); i++)
{
if (postfix[i] >= 48 && postfix[i] <= 57)
mypush(postfix[i]-'0');
else if (postfix[i] >= 42 && postfix[i] <= 47)
{
a=mypop();
b=mypop();
switch(postfix[i])
{
case '+':
mypush(a+b);
break;
case '-':
mypush(a-b);
break;
case '*':
mypush(a*b);
break;
case '/':
mypush(a/b);
break;
}
}
}
cout<<endl;
cout<<"ans is "<<mypop()<<endl;
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.