Здравствуйте.
Когда-то давно написал реализацию алгоритма преобразования выражения в обратную польскую нотацию и ее подсчета. Класс писался на скорую руку, где-то за час. Посему не реализовал все, что хотел, а именно поддержку:
1) Унарных операций
2) Функций
Сейчас пытаюсь придумать, как реализовать поддержку вышестоящих пунктов. Прошу помочь с алгоритмом.
Сам класс:
rpn.h:
Код:
#ifndef RPN_H_INCLUDED
#define RPN_H_INCLUDED
#include <stdlib.h>
#include <string>
#include <map>
#include <stack>
#include <sstream>
using namespace std;
//Класс исключений
class Exception
{
public:
class DifferentNumberOfBrackets{};
class FewVariables{};
class UnknownOperation{};
};
class RPN
{
public:
RPN(string s);
void calculate();
double getResult();
string getRPN();
void setRPN(string s);
private:
string rpn;
float result;
bool isNumber(string s);
void precalc(string& s);
};
#endif // RPN_H_INCLUDED
rpn.cpp:
Код:
#include "rpn.h"
//Dear future me, please forgive me if you can.
RPN::RPN(string s)
{
rpn = "";
precalc(s);
map<char,int> prior;
stack<char> st;
prior['('] = 0;
prior[')'] = 1;
prior['+'] = 2;
prior['-'] = 2;
prior['*'] = 3;
prior['/'] = 3;
string temp = "";
string out = "";
map<char,int>::iterator j;
for (unsigned int i = 0; i<s.length(); i++)
{
bool flag = false;
for (j = prior.begin(); j!=prior.end(); j++)
{
if (s[i]==(*j).first)
{
flag = true;
if (temp!="")
out += out!=""?" "+temp:temp;
temp = "";
break;
}
}
if (!flag)
{
temp.push_back(s[i]);
}
else
{
if (st.empty() || prior[s[i]]==0 || prior[st.top()]<prior[s[i]])
{
st.push(s[i]);
}
else if(prior[s[i]]==1)
{
while (!st.empty() && prior[st.top()]!=0)
{
out += out!=""?" ":"";
out.push_back(st.top());
st.pop();
}
if (st.empty()) throw Exception::DifferentNumberOfBrackets();
st.pop();
}
else if (prior[st.top()]>=prior[s[i]])
{
while (!st.empty() && prior[st.top()]>=prior[s[i]])
{
out += out!=""?" ":"";
out.push_back(st.top());
st.pop();
}
st.push(s[i]);
}
}
}
if (temp!="")
out += out!=""?" "+temp:temp;
while (!st.empty())
{
if (prior[st.top()]==0) throw Exception::DifferentNumberOfBrackets();
out += out!=""?" ":"";
out.push_back(st.top());
st.pop();
}
rpn = out;
}
void RPN::calculate()
{
if (rpn.length()==0) return;
istringstream tmp(rpn);
string s;
stack<double> st;
while(getline(tmp, s, ' '))
{
if (isNumber(s))
{
st.push(atof(s.c_str()));
} else
{
if (st.size()<2) throw Exception::FewVariables();
double k=st.top();
st.pop();
double m=st.top();
st.pop();
switch (s[0])
{
case '+': st.push(m+k); break;
case '-': st.push(m-k); break;
case '*': st.push(m*k); break;
case '/': st.push(m/k); break;
default: throw Exception::UnknownOperation(); break;
}
}
}
result = st.top();
}
void RPN::precalc(string& s)
{
while (s.find('.')<s.length())
s.replace(s.find('.'),1,",");
while (s.find(' ')<s.length())
s.replace(s.find(' '),1,"");
if (s=="") s="0";
if (s[0]=='-')
s = "0" + s;
unsigned int i = 0;
while (i<s.length())
if ((s[i] == '(') && (s[i+1] == '-'))
s.insert(i+1,"0");
else
i++;
}
bool RPN::isNumber(string s)
{
return s[0]>='0' && s[0]<='9';
}
double RPN::getResult()
{
return result;
}
string RPN::getRPN()
{
return rpn;
}
void RPN::setRPN(string s)
{
rpn = s;
}
Пример использования:
Код:
#include <iostream>
#include "rpn.h"
int main()
{
RPN* rpn = new RPN("(44+1)*(4+6)");
cout<<rpn->getRPN()<<endl;
rpn->calculate();
cout<<rpn->getResult()<<endl;
return 0;
}