データ構造学習ノートのスタック(デジタル変換、括弧マッチング、表式求値逆ポーランド)
8225 ワード
#include
#include
#include
#include
#include
#include //gcc6.3
#include
#include
using namespace std;
typedef int Rank;
#define DEFAULT_CAPACITY 3
#define N_OPTR 9
const char OPSET[N_OPTR] = { '+', '-', '*', '/', '^', '!', '(', ')', '\0' };
const char pri[N_OPTR][N_OPTR] = {
// ，
// + - * / ^ ! ( ) \0
/* +*/'>', '>', '', '>',
/* -*/'>', '>', '', '>',
/* **/'>', '>', '>', '>', '', '>',
/* /*/'>', '>', '>', '>', '', '>',
/* ^*/'>', '>', '>', '>', '>', '', '>',
/* !*/'>', '>', '>', '>', '>', '>', ' ', '>', '>',
/* (*/'
class Stack {
private:
Rank _top;
Rank _buttom;
int _capacity;
T *_elem;
protected:
void expand();
void shrink();
public:
Stack(int c = DEFAULT_CAPACITY);
~Stack();
Rank GetSize();
bool isEmpty();
void push(T const &e);
T pop();
T &top();
void show();
};
template
Stack::Stack(int c)
{
_elem = new T[_capacity = c];
_buttom = 0;
_top = 0;
}
template
Stack::~Stack()
{
delete[] _elem;
}
template
Rank Stack::GetSize()
{
return _top - _buttom;
}
template
bool Stack::isEmpty()
{
return (_top == _buttom) ? true : false;
}
template
void Stack::expand()
{
_capacity = max(_capacity, DEFAULT_CAPACITY);
T *oldelem = _elem;
_elem = new T[_capacity <<= 1];
for (int i = 0; i < GetSize(); ++i)
_elem[i] = oldelem[i];
delete[] oldelem;
}
template
void Stack::push(T const &e)
{
if (GetSize() >= _capacity) expand();
_elem[_top++] = e;
}
template
T &Stack::top()
{
return _elem[_top - 1];
}
template
void Stack::shrink()
{
//cout<
T Stack::pop()
{
_top--;
if (GetSize() * 2 < _capacity) shrink();
return _elem[_top];
}
template
void Stack::show()
{
cout << "top: " << _top << "\tbuttom: " << _buttom << endl;
cout << "size: " << GetSize() << "\tcapacity: " << _capacity << endl;
for (int i = 0; i < GetSize(); ++i)
cout << _elem[i] << "\t";
cout << endl;
}
// n b ( )
void convert(Stack &s, int n, int b)
{
static char digit[] = { '0', '1', '2', '3', '4', '5',
'6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
while (n > 0)
{
s.push(digit[n%b]);
n /= b;
}
}
//
bool paren(const char exp[])
{
Stack s;
for (int i = 0; i < strlen(exp); ++i)
{// ， pop。
if ('(' == exp[i])s.push(exp[i]);
else if (!s.isEmpty() && ')' == exp[i])s.pop();
else if (s.isEmpty() && ')' == exp[i])return false;
}
return s.isEmpty();// ，
}
// (2n)!/((n+1)!n!)
// 123 312 ( )
template
bool permutation(Stack &s, const T exp[], int expSize)
{//s.pop() -> exp[] s ， push
if (expSize != s.GetSize()) return false;
Stack t;
for (int i = 0, j = 0; i < expSize; ++i)
{
t.push(s.pop());
while (t.GetSize() > 0 && t.top() == exp[j])
{
t.pop();
j++;
}
}
return (t.isEmpty() == true) ? true : false;
}
// ， ，( evaluate)
void readNumber(char *&p, Stack& stk)
{
stk.push(float(*p - '0'));
while (isdigit(*(++p))) stk.push(stk.pop() * 10 + (*p - '0'));
if ('.' != *p)return;
float fraction = 1;
while (isdigit(*(++p)))stk.push(stk.pop() + (*p - '0')*(fraction /= 10));
}
// ( evaluate)
char orderBetween(char &e, char &s)
{
int i, j;
for (i = 0; i < N_OPTR; ++i)
if (e == OPSET[i])break;
for (j = 0; j < N_OPTR; ++j)
if (s == OPSET[j])break;
return pri[i][j];
}
// ( evaluate)
float calcu(float p1, char op, float p2 = 0)
{
switch (op) {
case '+':return p1 + p2;
case '-':return p1 - p2;
case '*':return p1 * p2;
case '/':return p1 / p2;
case '^': {
float c = 1;
while (p2--) c = c * p1;
return c;
}
case '!': {
if (p1 == 0)return 1;
else return p1 * calcu(p1 - 1, '!');//
}
}
}
//
void append(char *&rpn, float opnd)
{
int n = strlen(rpn);
char buf[64];
if (opnd != float(int(opnd)))sprintf(buf, "%.2f \0", opnd); //
else sprintf(buf, "%d \0", int(opnd)); //
rpn = (char*)realloc(rpn, sizeof(char)*(n + strlen(buf) + 1)); // , stdlib.h malloc.h
strcat(rpn, buf); //RPN
}
//
void append(char *& rpn, char optr) { // RPN
int n = strlen(rpn); //RPN （ '\0' ， n + 1）
rpn = (char*)realloc(rpn, sizeof(char) * (n + 3)); //
sprintf(rpn + n, "%c ", optr); rpn[n + 2] = '\0'; //
}
//
float evaluate(char *S, char *& rpn)//*&
{
Stack opnd;//
Stack optr;//
optr.push('\0');// ， '\0'
int i = 0;
while (!optr.isEmpty())
{
if (isdigit(*S))// ,isdigit 10
{
readNumber(S, opnd);//
append(rpn, opnd.top());
}
else switch (orderBetween(optr.top(), *S))//
{
case '': {
char op = optr.pop();
append(rpn, op);
if (op == '!') {
float temp = calcu(opnd.top(), op);//
opnd.pop();
opnd.push(temp);
}
else {
float pOpnd2 = opnd.top();
opnd.pop();
float pOpnd1 = opnd.top();
opnd.pop();
opnd.push(calcu(pOpnd1, op, pOpnd2));//
}
break;
}
}
}
return opnd.top();
}
int main()
{
Stack s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.show();
cout << s.isEmpty() << endl;
cout << s.top() << endl;
cout << s.pop() << endl;
s.show();
cout << s.top() << endl;
cout << s.pop() << endl;
s.show();
cout << s.top() << endl;
cout << s.pop() << endl;
s.show();
cout << s.top() << endl;
cout << s.pop() << endl;
cout << s.isEmpty() << endl;
s.show();
cout << endl;
Stack c;
convert(c, 2013, 2);
while (!c.isEmpty())cout << c.pop();
cout << endl;
char a[] = "adwasfweef";
cout << paren(a);
char b[] = "(!c.isEmpty())cout< si;
for (int i = 5; i > 0; i--) si.push(i);
int arri[] = { 4, 5, 3, 2, 1 };
cout << permutation(si, arri, 5);
Stack s2;
for (int i = 5; i > 0; i--) s2.push(i);
int arr2[] = { 1, 5, 3, 2, 4 };
cout << permutation(s2, arr2, 5) << endl;
char *r = (char*)malloc(sizeof(char) * 1);
r[0] = '\0';
char exp1[] = "2+2";
char exp2[] = "20*(4.5-3)";
char exp3[] = "5!-6.7";
char exp4[] = "(1+2^3!-4)*(5!-(6-(7-(89-0!))))";
cout << evaluate(exp1, r) << endl;
cout << r << endl;
r[0] = '\0';
cout << evaluate(exp2, r) << endl;
cout << r << endl;
r[0] = '\0';
cout << evaluate(exp3, r) << endl;
cout << r << endl;
r[0] = '\0';
cout << evaluate(exp4, r) << endl;
cout << r << endl;
return 0;
}