# 【顺序栈的应用】求逆波兰、任意进制转换、括号匹配

//顺序表实现栈并且检验，后缀表达式求值，数制转换、括号匹配
#include <iostream>
#include <string>
#include <sstream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int stackSize = 200;//假设栈的初始大小为200
void BracketsMatch();			//括号匹配
void ConvertNum();		//进制转换
void Inverse_expression();		 //后缀(逆波兰)表达式求值
template<class T>
class SeqStack
{
public:
SeqStack() { top = -1; }
void push(T x);
T pop();
T getTop();
bool isEmpty();
private:
T data[stackSize];
int top;//栈顶指针
};
int main()
{
int select;
while (true)
{
cout << "输入数字选择功能" << endl
<< "->1.后缀表达式求值" << endl
<< "->2.任意进制转换" << endl
<< "->3.括号匹配" << endl
<< "->4.清屏" << endl
<< "->5.退出" << endl;
cin >> select;
string temp;//吸收空格
getline(cin,temp);
switch (select)
{
case 1:
Inverse_expression();//逆波兰测试
break;
case 2:
ConvertNum();//进制转换测试
break;
case 3:
BracketsMatch();//括号匹配测试
break;
case 4:
system("cls");
break;
case 5:
return 0;
break;
default:
cout << "错误" << endl;
}
}

}

template<class T>
void SeqStack<T>::push(T x)
{
if (top == stackSize - 1)
{
cout << "栈溢出" << endl;
throw "error";
}
else
{
data[++top] = x;
}
}

template<class T>
T SeqStack<T>::pop()
{
if (top == -1)
{
cout << "栈下溢" << endl;
throw "error";
}
else
{
T x = data[top--];
return x;
}
}

template<class T>
T SeqStack<T>::getTop()
{
if (top == -1)
{
cout << "当前栈空" << endl;
throw "error";
}
else
{
T x = data[top];
return x;
}
}

template<class T>
bool SeqStack<T>::isEmpty()
{
}

void BracketsMatch()
{
string str;
SeqStack<char> sta;
cout << "输入括号序列" << endl;
cin >> str;
for (int i = 0; i < str.length(); i++)
{
switch (str.at(i))
{
case '{':
case '[':
case '(':
sta.push(str.at(i));
break;
case ')':
case ']':
case '}':
if (sta.isEmpty())
{
cout << "右括号多了" << endl;
return;
}
else
{
char a = sta.getTop(), b = str.at(i);
if (a == '('&&b == ')' || a == '['&&b == ']' || a == '{'&&b == '}')
{
sta.pop();
break;
}
else { cout << "匹配失败" << endl; return; }
}
}
}
if (sta.isEmpty()) cout << "完美匹配" << endl;
else
{
cout << "左括号多了" << endl;
}
return;
}

void ConvertNum()
{
SeqStack<int> sta;
int scale, base, e;
cout << "请输入数制转换的进制及数值：" << endl;
cin >> scale >> base;
cout << "数值" << base << "的" << scale << "进制为：" << endl;
while (base)
{
sta.push(base%scale);
base /= scale;
}
while (!sta.isEmpty())
{
cout << sta.pop();
}
cout << endl;
}

void Inverse_expression()
{
SeqStack<double> sta;
cout << "输入需要求值的后缀(逆波兰)表达式" << endl;
string str;
getline(cin,str);
stringstream strInput;
strInput << str;
string x;
while (strInput >> x)
{
if (x=="+")
{
double a = sta.pop();
double b = sta.pop();
sta.push(a+b);
}
else if (x=="-")
{
double a = sta.pop();
double b = sta.pop();
sta.push(a - b);
}
else if (x=="*")
{
double a = sta.pop();
double b = sta.pop();
sta.push(a * b);
}
else if (x=="/")
{
double a = sta.pop();
double b = sta.pop();
sta.push(a / b);
}
else
{
sta.push(atof(x.c_str()));
}
}
cout << sta.pop() << endl;
}