Доброго времени суток!
Надо с помощью стека на динамическом массиве реализовать перевод инфиксного выражения в постфиксное. (обратная польская нотация). с помощью алгоритма сортировочной станции.
Кто не знает или забыл, что это такое, например:
дано выражение (4+5)*7
45+7* - это обратная польская запись (постфиксное выражение)
У меня почему-то не записываются все операции в стек, в чем ошибка в программе?
| Код |
#include <conio.h>
#include <stdio.h>
#include <iostream>
using namespace std;
char opers[5]={'+', '-', '*', '/', '('};
int priors[5]={1, 1, 2, 2, 0};
class Stack {
private:
char* arr; // Указатель на динамический массив с элементами стека
char* top; // Указатель на верх стека
int size; // Емкость стека
public:
Stack(int s = 10)
{ // Конструктор с одним параметром по умолчанию
// Этот конструктор, в частности, заменяет и конструктор по умолчанию
this->size = s;
arr = new char[s];
top = arr;
}
Stack(const Stack& s)
{ // Копирующий конструктор
this->size = s.size;
this->arr = new char[s.size]; // Создаём НОВЫЙ динамический массив
this->top = arr;
char* p = s.arr; // Отдельный указатель на элементы старого массива
while (p < s.top)
{
*top++ = *p++; // Копируем элементы и позицию в новый массив
}
}
bool isEmpty()
{ // Метод проверяющий пуст ли стек
if (top <= arr) {
return true;
} else {
return false;
}
}
bool isFull()
{ // Метод проверяющий полон ли стек
if (top - arr >= size) {
return true;
} else {
return false;
}
}
void push(char val)
{ // Метод добавляющий элемент в стек
if(!isFull()) {
*top = val;
top++;
} else {
cout << "Stack full!" << endl; // Стэк полон
}
}
char pop()
{ // Метод извлекающий верхний элемент из стека
if(!isEmpty())
{
top--;
return *top;
}
else
{
return 0; // Стэк пуст, вернём нуль
}
}
void printStack()
{ // Метод выводящий элементы стека в строку
char* p = arr;
while (p < top)
{
cout << *p++ << ' ';
}
cout << endl;
}
~Stack()
{ // Деструктор
delete[] arr; // Освобождает память от массива
};
};
//===============================================================================================================
int Prior(char op1, char op2)
{
int op1p, op2p, i;
op1p=0;
op2p=0;
for (i=0; i< 5; i++)
{
if(op1==opers[i])
op1p=i;
if(op2==opers[i])
op2p=i;
}
if(priors[op1p]<=priors[op2p])
return 1;
return 0;
}
int IsDigit(char c) // Если число
{
if( (c>= '0') && (c<='9'))
return 1;
return 0;
}
int IsOper(char c) // Если операнд
{
for(int i=0; i<5; i++)
{
if(c == opers[i])
return 1;
}
return 0;
}
int IsOpBr(char c) // Если открывающая скобка
{
if(c=='('||c=='['||c=='{')
return 1;
return 0;
}
int IsClBr(char c) // Если закрывающая скобка
{
if(c==')'||c==']'||c=='}')
return 1;
return 0;
}
void main()
{
char inexpr[80];
char outexpr[80];
int k, point; // Счетчики
Stack Poland; // Инициализация стека
char c;
int i, j, x;
i=0;
j=0;
printf("Enter an expression\n");
scanf("%s", inexpr);
while(inexpr[i]!='\0')
{
if(IsDigit(inexpr[i]))
{
outexpr[j]=inexpr[i];
j++;
}
if(IsOpBr(inexpr[i]))
{
Poland.push(inexpr[i]);
}
if(IsClBr(inexpr[i]))
{
c = Poland.pop();
while(!IsOpBr(c))
{
outexpr[j]=c;
c = Poland.pop();
j++;
}
}
if(IsOper(inexpr[i]) && (inexpr[i]!='('))
{
outexpr[j]=' ';
j++;
x = c = Poland.pop();
if (x == 1)
{
while (Prior(inexpr[i], c))
{
outexpr[j]=c;
j++;
x = c = Poland.pop();
if (x == 0)
break;
}
}
if( x!= 0)
Poland.push(c);
Poland.push(inexpr[i]);
}
i++;
}
while ( outexpr[j] == Poland.pop())
j++;
outexpr[j]='\0';
printf("%s", outexpr);
getch();
}
|
|