Я пишу программу, которая преобразует инфикс в постфикс (через стек, реализуемый связанным списком), хранящийся в массиве символов и оценивающий постфиксное выражение. Прекрасно работает до конвертации.
Но когда я вызываю функцию для оценки постфиксного выражения, она дает неверные ответы.
Проблема начинается с того момента, когда функция evalPfExpression() класса expEvaluator выводит число из массива символов postfix. (выделено через комментарии капитала в коде).
Сначала он дал совершенно неправильные цифры. Но вычитание 48 из каждого числа фиксировало его на отдельные цифры. (Заметила, что каждая цифра дана с 48 добавленными). Но он по-прежнему дает неправильные ответы для 2-значных или более высоких чисел. Я предполагаю, что это может быть связано с преобразованием типов "char" и "int".
Поблагодарили бы за помощь.
#include <iostream>
#include <conio.h>
using namespace std;
////The node of the stack:
class node
{
public:
char value;
node* next;
};
////The basic stack class:
class stack
{
public:
int size;
node* top;
stack() //default constructor for stack
{
size=0;
top=NULL;
}
void push(char);
char pop();
char topstack();
void print();
bool isEmpty();
};
//Stack push function:
void stack::push(char e)
{
node *temp;
temp =new node;
temp->next = top;
temp->value=e;
top=temp;
size++;
}
//Stack pop function:
char stack::pop()
{
char d;
if (isEmpty())
{
cout<<"\nStack is Empty\n";
return '!';
}
else
{
node *temp = top;
top=top->next;
d=temp->value;
delete temp;
size--;
}
return d;
}
//Returns a copy of the stack top element.
char stack::topstack()
{
if(size==0)
return '\0';
else
return top->value;
}
//To print the stack members.
void stack::print()
{
cout<<"PRINTING STACK\n";
int s=size;
for(int i=0; i<s; i++)
cout<< pop() <<"\n";
}
//Function to determine whether the stack is empty. Returns true for empty.
bool stack::isEmpty()
{
if(size==0)
{
return true;
}
return false;
}
////Class, the instance of which will convert infix to postfix.
class expEvaluator
{
public:
char infix[50];
char postfix[50];
int ps; //counter variable to be used for index of the postfix array.
stack s; //The stack through which the operations will be performed.
expEvaluator() //Constructor.
{
ps=0;
}
bool isOp(char a)//Function to determine whether the character is an operator.
{
if(a=='+' || a=='-' || a=='*' || a=='/' || a=='^' || a=='%' )
return true;
else
return false;
}
bool precedence(char a, char b)//To determine the precedence of operators. True means 'a' is of same or lower precedence than 'b'.
{
if(a=='+' || a=='-')
return true;
else if (a=='*' || a=='/')
{
if(b=='+' || b=='-')
return false;
else if(b=='*' || b=='/')
return true;
}
}
//The function that will convert the given infix statement to postfix.
void convertToPostfix()
{
int l=0; //To keep count of the number of characters entered in infix form.
cout<<"Enter Infix expression: ";
cin>>infix;
for(int i=0; infix[i]!='\0'; i++)
{
l++;
}
for(int i=0; i<l; i++)
{
if(infix[i]=='(')
s.push(infix[i]);
else if(isOp(infix[i])) //If character at infix[i] is an operator
{
while(isOp(s.topstack()) && precedence(infix[i], s.topstack())) //popping operators from stack to postfix array till operator of
{ //lower precedence is met.
postfix[ps]=s.pop();
ps++;
}
s.push(infix[i]); //then push the operator onto the stack.
}
else if(infix[i]==')') //if right bracket encountered.
{
while(s.topstack()!='(') //till left bracket is not encountered,
{
postfix[ps]=s.pop();
ps++; //keep popping elements to postfix array.
}
s.pop(); //pop left bracket when encountered.
}
else //if just an operand is encountered.
{
postfix[ps]=infix[i]; //copy to postfix array.
ps++;
}
}
while(!(s.isEmpty())) //When end of array is reached (the previous loop ends only then) and its not empty,
{
postfix[ps]=s.pop(); //pop all elements from stack onto the postfix array.
ps++;
}
postfix[ps]='\0';
cout << "POSTFIX:\n" << postfix;
}
//Function to calculate the result, when two operands and operator are passed to it.
int calculate(int op1, int op2, char operand)
{
if(operand == '+')
{
return op1 + op2;
}
else if(operand == '-')
{
return op1 - op2;
}
else if(operand == '*')
{
return op1 * op2;
}
else if(operand == '/')
{
return op1 / op2;
}
else if(operand == '%')
{
return op1 % op2;
}
else if(operand == '^')
{
return op1 ^ op2;
}
}
//Function to evaluate the postfix expression:
void evalPfExpression()
{
ps = 0;
while(postfix[ps]!='\0')
{
if (!isOp(postfix[ps]))
{
s.push(postfix[ps]);
ps++;
}
else if(isOp(postfix[ps]))
{//******NOT POPPING CORRECT VALUES.******
int x = s.pop() - 48; //Second operand.
int y = s.pop() - 48; //First operand.
cout << "Second operand: "<< x << " First op:" << y << endl;
int res = calculate(y, x, postfix[ps]); //The result of two operands calculation
s.push(res); //is returned to the variable 'res' and pushed
ps++; //to the stack
}
}
int result = s.pop(); //When '\0' is encountered, loop stops and the final result is popped
cout << "\nThe postfix statement evaluates to:\n" << result << endl;
}
};
//////////////////////////////////////////////////////////////////////////////////
int main(void)
{
expEvaluator e1;
e1.convertToPostfix();
e1.evalPfExpression();
getch();
return 0;
}
Нет ничего плохого в pop(). Это выскакивает то, что вы толкаете. Проблема в том, что вы толкаете.
Если вам нужны значения больше 255, вам нужно будет использовать "int", а не "char" в качестве типа значения в узле.
Вы подталкиваете самого персонажа, а не его ценность. Например, вы нажимаете "0", а не 0. Разница между ними - угадайте, что? 48.
Для многозначных чисел вам нужно нажать результат некоторой функции, такой как atoi() на строку, которую вы хотите разбор в качестве числа.