Давно уже ломаю голову над задачей. Эта программа вычисляет выражение типа 2+3*4/3-2. В выражение могут быть только одноразрядные числа типа int или операции + - * / .Программа работает так (далее цитата из учебника):_____________________________________________________________________________________________________________
Если символ представляет собой число, то мы помещаем его в стек. Туда же мы поместим первую из встретившихся нам операций. Вся хитрость заключается в том, как составить последовательность операций. Заметим, что мы не выполняем действие текущей операции, так как мы еще не знаем, какое за ней следует число. Найденная операция является сигналом, что мы не можем выполнять предыдущую операцию, которая помещена в стек. Так, если в стеке последовательность 2 + 3, то перед выполнением сложения мы должны найти следующую операцию.
Таким образом, когда мы поняли, что текущий символ является операцией (за исключением первого), мы извлекаем из стека предыдущее число (3 в нашем примере) и предыдущую операцию (+) и помещаем их в переменные lastval и lastop. Наконец мы извлекаем первое число (2) и выполняем арифметическую операцию с двумя числами (получая 5). Всегда ли мы можем выполнить предыдущую операцию? Нет. Вспомним, что * и / имеют более высокий приоритет, чем + и -. В выражении 3+4/2 мы не можем выполнить сложение пока не произведем деление.
С другой стороны, если текущая операция + или -, то мы всегда можем выполнить предыдущую операцию. Так, когда мы встретим +в выражении 4-5+6, то мы можем выполнить предыдущую операцию - , а когда мы увидим - в выражении 6/2-3, то мы можем выполнить деление. В этой таблице отражены четыре возможных случая...
- Предыдущий оператор Текущий оператор Пример Действие 1
- + или - * или /1 3+4/ Положить в стек предыдущий оператор
и предыдущее число
- * или / * или / 9/3* Выполнить предыдущий оператор, положить
в стек результат (3)
- + или - + или - 6+3+ Выполнить предыдущий оператор, положить
в стек результат (9)
- * или / + или - 8/2 Выполнить предыдущий оператор, положить в стек
результат (4)
Метод parse() выпоняет этот процесс, последовательно обрабатывая полученное выражение и выполняя операции. Но здесь много работы. В стеке все еще содержится или одно число, или несколько последовательностей число-операция-число. Обрабатывая содержимое стека, мы выполняем операции этих последовательностей. Наконец в стеке останется одно число; оно будет значением первоначального выражения. Метод solve() выполняет все выше перечисленные действия до тех пор, пока в стеке не останется одно число. Проще говоря, метод parse() помещает элементы выражения в стек, а метод solve() извлекает их.
Вот сама программа:
| Код |
// parse.cpp
// evaluates arithmetic expressions composed of 1-digit numbers
#include <iostream>
#include <cstring> //for strlen(), etc
using namespace std;
const int LEN = 80; //length of expressions, in characters
const int MAX = 40; //size of stack
////////////////////////////////////////////////////////////////
class Stack
{
private:
char st[MAX]; //stack: array of chars
int top; //number of top of stack
public:
Stack() //constructor
{ top = 0; }
void push(char var) //put char on stack
{ st[++top] = var; }
char pop() //take char off stack
{ return st[top--]; }
int gettop() //get top of stack
{ return top; }
};
////////////////////////////////////////////////////////////////
class express //expression class
{
private:
Stack s; //stack for analysis
char* pStr; //pointer to input string
int len; //length of input string
public:
express(char* ptr) //constructor
{
pStr = ptr; //set pointer to string
len = strlen(pStr); //set length
}
void parse(); //parse the input string
int solve(); //evaluate the stack
};
//--------------------------------------------------------------
void express::parse() //add items to stack
{
char ch; //char from input string
char lastval; //last value
char lastop; //last operator
for(int j=0; j<len; j++) //for each input character
{
ch = pStr[j]; //get next character
if(ch>='0' && ch<='9') //if it's a digit,
s.push(ch-'0'); //save numerical value
//if it's operator
else if(ch=='+' || ch=='-' || ch=='*' || ch=='/')
{
if(s.gettop()==1) //if it's first operator
s.push(ch); //put on stack
else //not first operator
{
lastval = s.pop(); //get previous digit
lastop = s.pop(); //get previous operator
//if this is * or / AND last operator was + or -
if( (ch=='*' || ch=='/') &&
(lastop=='+' || lastop=='-') )
{
s.push(lastop); //restore last two pops
s.push(lastval);
}
else //in all other cases
{
switch(lastop) //do last operation
{ //push result on stack
case '+': s.push(s.pop() + lastval); break;
case '-': s.push(s.pop() - lastval); break;
case '*': s.push(s.pop() * lastval); break;
case '/': s.push(s.pop() / lastval); break;
default: cout << "\nUnknown oper"; exit(1);
} //end switch
} //end else, in all other cases
s.push(ch); //put current op on stack
} //end else, not first operator
} //end else if, it's an operator
else //not a known character
{ cout << "\nUnknown input character"; exit(1); }
} //end for
} //end parse()
//--------------------------------------------------------------
int express::solve() //remove items from stack
{
char lastval; //previous value
while(s.gettop() > 1)
{
lastval = s.pop(); //get previous value
switch( s.pop() ) //get previous operator
{ //do operation, push answer
case '+': s.push(s.pop() + lastval); break;
case '-': s.push(s.pop() - lastval); break;
case '*': s.push(s.pop() * lastval); break;
case '/': s.push(s.pop() / lastval); break;
default: cout << "\nUnknown operator"; exit(1);
} //end switch
} //end while
return int( s.pop() ); //last item on stack is ans
} //end solve()
////////////////////////////////////////////////////////////////
int main()
{
char ans; //'y' or 'n'
char string[LEN]; //input string from user
cout << "\nEnter an arithmetic expression"
"\nof the form 2+3*4/3-2."
"\nNo number may have more than one digit."
"\nDon't use any spaces or parentheses.";
do {
cout << "\nEnter expresssion: ";
cin >> string; //input from user
express* eptr = new express(string); //make expression
eptr->parse(); //parse it
cout << "\nThe numerical value is: "
<< eptr->solve(); //solve it
delete eptr; //delete expression
cout << "\nDo another (Enter y or n)? ";
cin >> ans;
} while(ans == 'y');
system("PAUSE");
return 0;
}
|
____________________________________________________________________________________________________________
Проблема состоит в том, что надо доработать эту программу, чтобы она вычисляла значение с рациональными числами float, а не только с одноразрядными.
Вот задание из учебника:_____________________________________________________________________________________________________________
Попробуйте доработать программу, чтобы она могла вычислять значения математических выражений с рациональными числами, например типа float, а не только с одноразрядными числами:
3.14159 / 2.0 + 75.25 * 3.333 + 6.02
Во-первых, нужно развить стек до такой степени, чтобы он мог хранить и операторы (типа char), и числа (типа float). Но как, спрашивается, можно хранить в стеке значения двух разных типов? Ведь стек - это, по сути дела, массив. Надо еще учесть, что типы char и float даже не совпадают по размеру! Даже указатели на разные типы данных (char* и float*) компилятор не позволит хранить в одном массиве, не смотря на то, что они одинакового размера. Единственный способ хранить в массиве два разных типа указателей - сделать эти типы наследниками одного и того же базового класса. При этом базовому классу даже нет нужды иметь какие-то собственные данные, это может быть абстрактный класс, из которого никакие объекты создаваться не будут.
Конструкторы могут хранить значения в порожденных классах обычным способом, но должна иметься специальная чистая виртуальная функция для того, чтобы извлечь эти значения. Представляем возможный сценарий работы над этим вопросом...
| Код |
class Token
{
public:
virtual float getNumber()=0;
virtual char getOperator()=0;
};
class Operator : public Token
{
private:
char oper;
public:
Operator(char);
char getOperator();
float getNumber();
};
class Number : public Token
{
private:
float fnum;
public:
Number(float);
float getNumber();
char getOperator();
};
Token* atoken[100];
|
Виртуальные функции базового класса должны быть реализованы во всех порожденных классах, в противном случае классы становятся абстрактными. Таким образом, классу Operand нужна функция getNumber(), несмотря на то, что она фиктивная. Классу Number нужна функция getOperand(), несмотря на то, что она тоже фиктивная.
Поработайте над этим каркасом, сделайти его реально работающей программой, добавив класс Stack, содержащий объекты класса Token, и функцию main(), в которой бы заносились в стек и извлекались из него разные арифметические операторы и числа в формате с плавающей запятой.
______________________________________________________________________________________________________________
Я попробывал вести выражение типа 3.14159 / 2.0 + 75.25 * 3.333 + 6.02 в main(), в конструкторе express(char* ptr) класса express написал код, который отделяет + * - / от цифр. Разнес операции в один массив (типа char), а цифры в другой, тоже char(двухмерный), которые надо как-то перевести в double, но это не столь важно. Важно то, как эти два получившихся массива потом перевести в массив Token. Понятно, что все цифры надо заносить в массив Token через одну, и операции тоже. Например цифры занести в 0, 2, 4, 6 и т.д. элементы массива Token, а операции в 1, 3, 5-ый элементы. Но я абсолютно не понимаю как это сделать и надо ли это делать вообще?
Вот код, который я изуродовал. Класс Token со своими детьми пока лежит мертвым грузом. Из main() я убрал вызовы всех функций класса express через указатель *eptr (чтоб не мешали проверить код для отделения операций от чисел). Эта программа выводит отдельно числа и отдельно операторы.| Код |
#include <iostream>
#include <cstring>
using namespace std;
const int LEN = 80;
const int MAX = 40;
////////////////////////////////////////////////////////////////
class Token
{
public:
virtual float getNumber()=0;
virtual char getOperator()=0;
};
////////////////////////////////////////////////////////////////
class Operator : public Token
{
private:
char oper;
public:
Operator(char ch):oper(ch) {}
char getOperator();
float getNumber();
};
////////////////////////////////////////////////////////////////
class Number : public Token
{
private:
float fnum;
public:
Number(float f):fnum(f) {}
float getNumber();
char getOperator();
};
////////////////////////////////////////////////////////////////
class Stack
{
private:
char st[MAX];
int top;
public:
Stack()
{ top = 0; }
void push(char var)
{ st[++top] = var; }
char pop()
{ return st[top--]; }
int gettop()
{ return top; }
};
////////////////////////////////////////////////////////////////
class express
{
private:
Stack s;
char* pStr;
int len;
public:
express(char* ptr)
{
pStr = ptr;
len = strlen(pStr);
char Nstr[100][100];
char CHstr[100];
int j, M, N, K;
int n=0;int m=0;int k=0;
for (j=0; j<len; j++)
{
if(*(pStr+j)=='+' || *(pStr+j)=='-' || *(pStr+j)=='*' || *(pStr+j)=='/')
{
CHstr[n++] = *(pStr+j);
k++;m=0;j++;
}
Nstr[k][m++] = *(pStr+j);
}
for(K=0; K<=k; K++)
{
for(M=0; M<m; M++){cout << Nstr[K][M];}
cout << " ";
}
cout << endl;
for(N=0; N<n; N++){cout << CHstr[N];}
}
void parse()
{
char ch;
char lastval;
char lastop;
for(int j=0; j<len; j++)
{
ch = pStr[j];
if(ch>='0' && ch<='9')
s.push(ch-'0');
else if(ch=='+' || ch=='-' || ch=='*' || ch=='/')
{
if(s.gettop()==1)
s.push(ch);
else
{
lastval = s.pop();
lastop = s.pop();
if( (ch=='*' || ch=='/') && (lastop=='+' || lastop=='-') )
{
s.push(lastop);
s.push(lastval);
}
else
{
switch(lastop)
{
case '+': s.push(s.pop() + lastval); break;
case '-': s.push(s.pop() - lastval); break;
case '*': s.push(s.pop() * lastval); break;
case '/': s.push(s.pop() / lastval); break;
default: cout << "\nUnknown oper"; exit(1);
}
}
s.push(ch);
}
}
else
{ cout << "\nUnknown input character"; exit(1); }
}
}
int solve()
{
char lastval;
while(s.gettop() > 1)
{
lastval = s.pop();
switch( s.pop() )
{
case '+': s.push(s.pop() + lastval); break;
case '-': s.push(s.pop() - lastval); break;
case '*': s.push(s.pop() * lastval); break;
case '/': s.push(s.pop() / lastval); break;
default: cout << "\nUnknown operator"; exit(1);
}
}
return int( s.pop() );
}
};
////////////////////////////////////////////////////////////////
int main()
{
char ans;
char string[LEN];
cout << "\nEnter an arithmetic expression"
"\nof the form 2+3*4/3-2."
"\nNo number may have more than one digit."
"\nDon't use any spaces or parentheses.";
cout << "\nEnter expresssion: ";
cin >> string;
express* eptr = new express(string);
system("PAUSE");
return 0;
}
|
Калькулятор. Разбор строки 
Загрузка ...
