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

一个栈的综合应用程序:

实现了求逆波兰、任意进制转换、括号匹配

//顺序表实现栈并且检验,后缀表达式求值,数制转换、括号匹配
#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()
{
  return top == -1 ? true :false;
}

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;
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

18 − 17 =