博客

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
char * midToAfterNums(char *s);
int main()
{
    char  *s = "(((35+15)*(80-70))/20)";
    s = midToAfterNums(s);
    cout<<s<<endl;
    return 0;
}
int getPriority(char ch)//只限于 +-*/(
{
    if(ch == '*'||ch == '/')
        return 2;
    else  if(ch == '(')
        return 0;
    else
        return 1;
}
char * midToAfterNums(char *s)
{
    vector<char>res;
    stack<char>symbol;
    for (int i=0; i<strlen(s); i++) {
        if ('0'<=s[i]&&s[i]<='9')
            res.push_back(s[i]);
        else{
            if (s[i] == '(')
                symbol.push(s[i]);
            else if( s[i] == ')')
            {
                while (true) {
                    char ch = symbol.top();
                    symbol.pop();
                    if(ch == '(')
                        break;
                    else
                        res.push_back(ch);
                }
            }
            else{
                if(symbol.empty())
                    symbol.push(s[i]);
                else
                {
                    if(getPriority(s[i])>=getPriority(symbol.top()))
                        symbol.push(s[i]);
                    else{
                        while (!symbol.empty()) {
                            if(getPriority(s[i])>=getPriority(symbol.top()))
                            {
                                symbol.push(s[i]);
                                break;
                            }
                            else{
                                res.push_back(symbol.top());
                                symbol.pop();
                            }
                        }
                        if (symbol.empty()) {
                            symbol.push(s[i]);
                        }
                    }
                }
            }
        }
    }
    while (!symbol.empty()) {
        res.push_back(symbol.top());
        symbol.pop();
    }
    char * str = new char[res.size()*2+1];
    int j = 0;
    for (int i=0; i<res.size(); i++) {
        str[j++] = res[i];
        str[j++] = ' ';
    }
    str[j]='\0';
    return str;
}