论坛 › 数据结构与算法 › 逆波兰表达式c++代码

Sj中国智造 发表于 2018-3-30 16:09:54

逆波兰表达式c++代码

本帖最后由 Sj中国智造 于 2018-3-31 08:43 编辑

/*---------------------------------------------
                中缀表达式转后缀表达式
                        逆波兰表达式
----------------------------------------------*/
#include <iostream>
#include <string>
#include <sstream>
#include <windows.h>

#define MAX_SIZE 1024
#define TRUE1
#define FALSE0
using namespace std;

template <class T>
class sqStack
{
public:
        sqStack();//申请一块内存
        ~sqStack();//释放申请的内存
        int isEmpty();//判断栈是否为空
        T push(T element);//压栈
        T pop();//弹栈

private:
        T * top;//头指针
        T *base;//底指针
};

template <class T>
sqStack<T>::sqStack()
{
        this->base = this->top = new T;
}

template <class T>
sqStack<T>::~sqStack()
{
        delete[] this->base;
}

template<class T>
int sqStack<T>::isEmpty()
{
        if (this->top == this->base)
        {
                return TRUE;
        }
        else return FALSE;
}

template <class T>
T sqStack<T>::push(T element)
{
        this->top++;
        *(this->top) = element;
        return *(this->top);
}

template <class T>
T sqStack<T>::pop()
{
        if (!isEmpty())
        {
                this->top--;
                return *(this->top + 1);
        }
        return NULL;
}

int main()
{
        sqStack<int> stack1;//储存数字的栈
        sqStack<char>stack2;//储存操作符的栈
        int num;//数字
        int num1, num2;
        char oper;//操作符
        string input;//接受用户输入
        string conversionResult;//转化的结果
        int priority;//记录优先级

        cout << "请输入表达式(以回车表示结束)：";
        getline(cin, input);//接收用户输入

        istringstream in(input);
        ostringstream out(conversionResult);

        priority = 0;
        while (1)
        {
                while (in.peek() == ' ') in.ignore(MAX_SIZE, ' ');//跳过空格
                if (in.eof()) break;

        if (in.peek() >= '0'&&in.peek() <= '9')
                {
                        in >> num;
                        out << num << ' ';
                }
                else
                {
                        in >> oper;
                        switch (oper)
                        {
                        case '+':
                        case '-':
                                if (1 > priority) stack2.push(oper);
                                else
                                {
                                        out << stack2.pop() << ' ';
                                        stack2.push(oper);
                                }
                                priority = 1; break;

                        case '*':
                        case '/':
                                if (2 > priority) stack2.push(oper);
                                else
                                {
                                        out << stack2.pop() << ' ';
                                        stack2.push(oper);
                                }
                                priority = 2; break;

                        case '(':
                                stack2.push(oper);
                                priority = 0; break;

                        case ')':
                                for (oper = stack2.pop(); oper != '(' ; oper = stack2.pop())
                                {
                                        out << oper << ' ';
                                        if (stack2.isEmpty())
                                        {
                                                std::cout << "括号不配对！" << endl;
                                                return -2;
                                        }
                                }
                                break;

                        default:
                                std::cout << "您输入的表达式格式有误或有非法字符！" << endl;
                                return -3;
                        }
                }
        }
        while (!stack2.isEmpty()) out << stack2.pop() << ' ';
        out << '#' << ends;

        conversionResult = out.str();

        in.clear();//清除eof()的设置
        in.str(conversionResult);

        while (in.peek() != '#')
        {
                while (in.peek() == ' ') in.ignore(MAX_SIZE, ' ');
                if (in.peek() == '#')break;

                if (in.peek() >= '0'&&in.peek() <= '9')
                {
                        in >> num;
                        stack1.push(num);//遇到数字就压栈
                }
                else
                {
                        in >> oper;//读取操作符
                        num1 = stack1.pop();
                        num2 = stack1.pop();
                        switch (oper)
                        {
                        case '+':
                                stack1.push(num1 + num2); break;
                        case '-':
                                stack1.push(num2 - num1); break;
                        case '/':
                                if (num1 == 0)
                                {
                                        cout << "除数不能为零！" << endl;
                                        return -4;
                                }
                                stack1.push(num2 / num1); break;
                        case '*':
                                stack1.push(num1*num2); break;
                        default:
                                cout << "程序出错!!"<<endl;
                                return -1;
                        }
                }
        }
        cout << "运算好的结果是：" << stack1.pop() << endl<<endl;
       
        cout << "10s后程序自动关闭！";
        Sleep(10000);
        return 0;
}
//主程序返回0说明一切正常
//返回-1说明程序计算出错
//返回-2说明括号不匹配
//返回-3说明输入表达式有误
//返回-4说明除数为0

看完小甲鱼的逆波兰表达式的程序，自己写了个c++实现代码，不足之处望批评指正!

小树呀 发表于 2021-9-20 19:58:35

大佬牛逼

查看完整版本: 逆波兰表达式c++代码