M24591:中序表达式转后序表达式

http://cs101.openjudge.cn/practice/24591/

思路：按照课上讲解，给符号设置等级即可，用时约20min，但是值得高兴的是一遍ac，我终于没在写bug了，代码也是十分高效，2ms

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution
{
    public:
        string s;
        vector<string> res;//以后缀表达式存储
        //给运算符设置等级
        bool isSymbal(char c)
        {
            return (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')');
        }
        int level(char c)
        {
            if (c == '*' || c == '/')
                return 2;
            if (c == '+' || c == '-')
                return 1;
            if (c == '(')
                return -1;
            return 0;
        }
        void get()
        {
            getline(cin, s);
        }
        void translate()
        {
            string temp="";
            vector<char> symbalStack;
            for (int i = 0; i < s.size(); i++)
            {
                if (isSymbal(s[i]))
                {
                    temp = "";
                    if (s[i] == '(')
                        symbalStack.push_back(s[i]);
                    else if (s[i] == ')')
                    {
                        while (!symbalStack.empty() && symbalStack.back() != '(')
                        {
                            temp = "";
                            temp += symbalStack.back();
                            symbalStack.pop_back();
                            res.push_back(temp);
                        }
                        symbalStack.pop_back();//去掉'('
                    }
                    else
                    {
                        while (!symbalStack.empty() && level(s[i]) <= level(symbalStack.back()))
                        {
                            temp = "";
                            temp += symbalStack.back();
                            symbalStack.pop_back();
                            res.push_back(temp);
                        }
                        symbalStack.push_back(s[i]);//将当前运算符入栈
                    }
                    temp = "";
                }
                else
                {
                    temp = "";
                    while (i < s.size() && !isSymbal(s[i]))
                    {
                        temp += s[i];
                        i++;
                    }
                    i--;//回退一步
                    res.push_back(temp);
                }
            }
            while (!symbalStack.empty())
            {
                temp = "";
                temp += symbalStack.back();
                symbalStack.pop_back();
                res.push_back(temp);
            }
        }
        void print()
        {
            for (int i = 0; i < res.size(); i++)
            {
                if (res[i]=="") continue;
                if(i) cout << " ";
                cout << res[i];
            }
            cout << endl;
        }
};


int main() 
{
    int N;
    cin >> N;
    cin.ignore();
    while (N--)
    {
        Solution s;
        s.get();
        s.translate();
        s.print();
    }
    return 0;
}

思路：我上网查了中序表达式转后序表达式的理论方法，自己编了程序。将数字直接加入结果，遇到运算符则将前面入栈的优先级不低于它的运算符全部弹出，随后将它入栈，最后把栈清空。每次调用.top()函数几乎都必须查找.empty()，不然就会RTE，需要注意。

#include<iostream>
#include<string>
#include<stack>
using namespace std;
int n;
string conv(string s) {
    stack<char> ss;
    string ans = "";
    for(int i = 0; i < s.size(); i ++) {
        if(s[i] == '(') ss.push('(');
        else if(s[i] == ')') {
            while(!ss.empty() && ss.top() != '(') {
                ans += ss.top();
                ans += ' ';
                ss.pop();
            }
            if(!ss.empty()) ss.pop();
        } else if(s[i] == '+' || s[i] == '-') {
            while(!ss.empty() && ss.top() != '(') {
                ans += ss.top();
                ans += ' ';
                ss.pop();
            }
            ss.push(s[i]);
        } else if(s[i] == '*' || s[i] == '/') {
            if(!ss.empty()) {
                while(ss.top() == '*' || ss.top() == '/') {
                    ans += ss.top();
                    ans += ' ';
                    ss.pop();
                    if(ss.empty()) break;
                }
            }
            ss.push(s[i]);
        }
        else {
            while((s[i] >= '0' && s[i] <= '9') || s[i] == '.') {
                ans += s[i];
                i ++;
            }
            i --;
            ans += ' ';
        }
    }
    while(!ss.empty()) {
        ans += ss.top();
        ans += ' ';
        ss.pop();
    }
    if(!ans.empty() && ans.back() == ' ')
        ans = ans.substr(0, ans.size() - 1);
    return ans;
}
string s;
int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) {
        cin >> s;
        cout << conv(s) << endl;
    }
    return 0;
}