Infix to Postfix & Evaluation of Postfix Expression

假设表达式中的数都是1位正整数。

#include <iostream>
#include <string>
#include <stack>
#include <cctype>

using namespace std;

void infixToPostfix(string &infix, string &postfix);
int isp(char c);
int icp(char c);
double calPostfix(string &postfix);

int main(){
    string infix, postfix;
    cin>>infix;
    infixToPostfix(infix, postfix);
    cout<<postfix<<endl<<calPostfix(postfix);
    return 0;
}

void infixToPostfix(string &infix, string &postfix){
    infix.push_back('#');
    stack<char> s;
    s.push('#');
    for(char c:infix){
    	if(c==' ') continue;
        if(isalnum(c)) postfix.push_back(c);
        else{
            if(icp(c)==isp(s.top())) s.pop(); //()，##相遇直接退栈
            else if(icp(c)<isp(s.top())){
                //退栈并输出，直到isp(栈顶)<=scp(c)
                while(icp(c)<isp(s.top())){
                    postfix.push_back(s.top());
                    s.pop();
                }
                if(icp(c)==isp(s.top())) s.pop();
                else s.push(c);
            }
            else{
                //入栈
                s.push(c);
            }
        }
    }
}

int isp(char c){
    if(c=='#') return 0;
    if(c=='(') return 1;
    if(c=='+' || c=='-') return 3;
    if(c=='*' || c=='/') return 5;
    if(c==')') return 6;
    return -1;
}

int icp(char c){
    if(c=='#') return 0;
    if(c=='(') return 6;
    if(c=='+' || c=='-') return 2;
    if(c=='*' || c=='/') return 4;
    if(c==')') return 1;
    return -1;
}

double calPostfix(string &postfix){
    stack<double> operands;
    for(char c:postfix){
        if(isdigit(c)) operands.push(double(c-'0'));
        else{
            double a = operands.top();
            operands.pop();
            double b = operands.top();
            operands.pop();
            if(c=='+') operands.push(b+a);
            else if(c=='-') operands.push(b-a);
            else if(c=='*') operands.push(b*a);
            else operands.push(b/a);
        }
    }
    return operands.top();
}

进阶版：支持超过1位的正整数的运算。转出的后缀表达式以空格分隔。

#include <iostream>
#include <string>
#include <stack>
#include <cctype>

using namespace std;

void infixToPostfix(string &infix, string &postfix);
int isp(char c);
int icp(char c);
double calPostfix(string &postfix);

int main(){
    string infix, postfix;
    getline(cin, infix);
    infixToPostfix(infix, postfix);
    cout<<postfix<<endl<<calPostfix(postfix);
    return 0;
}

void infixToPostfix(string &infix, string &postfix){
    infix.push_back('#');
    stack<char> s;
    s.push('#');
    int infix_len = infix.length();
    for(int i=0; i<infix_len; ){
        if(infix[i]==' '){
            i++;
            continue;
        }
        if(isdigit(infix[i])){
            while(isdigit(infix[i])) postfix.push_back(infix[i++]);
            postfix.push_back(' ');
        }
        else{
            if(icp(infix[i])==isp(s.top())) s.pop(); //()，##相遇直接退栈
            else if(icp(infix[i])<isp(s.top())){
                //退栈并输出，直到isp(栈顶)<=scp(infix[i])
                while(icp(infix[i])<isp(s.top())){
                    postfix.push_back(s.top());
                    postfix.push_back(' ');
                    s.pop();
                }
                if(icp(infix[i])==isp(s.top())) s.pop();
                else s.push(infix[i]);
            }
            else{
                //入栈
                s.push(infix[i]);
            }
            i++;
        }
    }
}

int isp(char c){
    if(c=='#') return 0;
    if(c=='(') return 1;
    if(c=='+' || c=='-') return 3;
    if(c=='*' || c=='/') return 5;
    if(c==')') return 6;
    return -1;
}

int icp(char c){
    if(c=='#') return 0;
    if(c=='(') return 6;
    if(c=='+' || c=='-') return 2;
    if(c=='*' || c=='/') return 4;
    if(c==')') return 1;
    return -1;
}

double calPostfix(string &postfix){
    stack<double> operands;
    int postfix_len = postfix.length();
    for(int i=0; i<postfix_len; ){
        if(postfix[i]==' '){
            i++;
            continue;
        }
        if(isdigit(postfix[i])){
            double c = 0;
            while(isdigit(postfix[i])){
                c = c * 10 + (postfix[i] - '0');
                i++;
            }
            operands.push(c);
        }
        else{
            double a = operands.top();
            operands.pop();
            double b = operands.top();
            operands.pop();
            if(postfix[i]=='+') operands.push(b+a);
            else if(postfix[i]=='-') operands.push(b-a);
            else if(postfix[i]=='*') operands.push(b*a);
            else operands.push(b/a);
            i++;
        }
    }
    return operands.top();
}