数据结构 中缀表达式转后缀表达式及其计算 V3.1

数据结构 中缀表达式转后缀表达式及其计算

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
template <typename T>
class SeqStack
{
    T data[100];
    int top;

public:
    SeqStack()
    {
        top = -1;
    }
    void Push(T x)
    {
        if (top == 99)
            return;
        top++;
        data[top] = x;
    }
    T Pop()
    {
        if (top == -1)
        {
            return 0;
        }
        T x = data[top];
        top--;
        return x;
    }
    T Top()
    {
        if (top == -1)
            return 0;
        return data[top];
    }
    int Empty()
    {
        return top == -1;
    }
    void clean()
    {
        top = -1;
    }
    void allPop(SeqStack &s)
    {
        while (top != -1)
        {
            cout << s.Pop() << ' ';
        }
    }
};
int first(char c)
{
    switch (c)
    {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return -1;
    }
}
void jisuan(string &s, SeqStack<char> &cc, SeqStack<double> &ii)
{
    double x, y;
    y = ii.Pop();
    x = ii.Pop();
    char fh = '0';
    fh = cc.Pop();
    if (fh == '+')
        ii.Push(x + y);
    else if (fh == '-')
        ii.Push(x - y);
    else if (fh == '*')
        ii.Push(x * y);
    else if (fh == '/')
        ii.Push(x / y);
}

int main()
{
    cout << "请输入中缀表达式:" << endl;
    SeqStack<char> cc;
    SeqStack<double> ii;
    string s;
    double t;
    cin >> s;
    cout << "转化的后缀表达式为:" << endl;
    int i, j, k;
    int f = 1;
    for (i = 0; i < s.length();)
    {
        if (s[i] == ' ')
            i++;
        if (s[i] >= '0' && s[i] <= '9')
        {

            ii.Push(s[i] - '0');
            cout << s[i++];
        }

        if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
        {
            if (cc.Empty() || (i > 0 && cc.Top() == '('))
            {
                cc.Push(s[i++]);
            }

            else if (first(cc.Top()) < first(s[i]))
            {
                cc.Push(s[i++]);
            }
            else
            {
                cout << cc.Pop();
            }
        }
        else if (s[i] == '(')
        {
            cc.Push(s[i++]);
        }

        else if (s[i] == ')')
        {
            while (cc.Top() != '(')
                cout << cc.Pop();
            cc.Pop();
            i++;
        }
    }
    while (!cc.Empty())
        cout << cc.Pop();
    cout << endl;
    ii.clean();
    cc.clean();
    for (i = 0; i < s.length();)
    {

        if (s[i] == ' ')
            i++;
        //大于9的数字运算
        else if (s[i] >= '0' && s[i] <= '9')
        {
            if (i > 0 && (s[i - 1] >= '0' && s[i - 1] <= '9'))
            {
                t = s[i++] - '0' + ii.Pop() * 10;
                ii.Push(t * f);
                f = 1;
            }
            else
            {
                ii.Push((s[i++] - '0') * f);
                f = 1;
            }
        }
        else if (f == 1 && (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/'))
        {
            if (cc.Empty())
            {
                cc.Push(s[i++]);
            }

            else if (first(cc.Top()) < first(s[i]))
            {
                cc.Push(s[i++]);
            }
            else
            {
                jisuan(s, cc, ii);
            }
        }
        else if (s[i] == '(')
        {
            cc.Push(s[i++]);
            if (s[i] == '-') // 负数表示
            {
                f = -1;
                i++;
            }
        }

        else if (s[i] == ')')
        {
            while (cc.Top() != '(')
                jisuan(s, cc, ii);
            cc.Pop();
            i++;
        }
    }
    while (!cc.Empty())
    {
        jisuan(s, cc, ii);
    }
    cout << ii.Pop();
}