中缀表达式转后缀表达式 规则

Modified on: Sun, 29 Nov 2020 10:32:02 +0800 热度: 1,601 度

(1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
(2) 从左至右扫描中缀表达式;
(3) 遇到操作数时,将其压入S2;
(4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
(4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
(4-2) 否则,若优先级比栈顶运算符的 高 ,也将运算符 压入 S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
(4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
(5) 遇到括号时:
(5-1) 如果是左括号“(”,则直接压入S1;
(5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
(6) 重复步骤(2)至(5),直到表达式的最右边;
(7) 将S1中剩余的运算符依次弹出并压入S2;
(8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。

#include <bits/stdc++.h>
using namespace std;
typedef struct expr_ele{
    int     type;       //0-数字, 1-操作符 -+ 2-操作符 */ 3-操作符 (
    char    op;         // -+*/(
    double  num;
}expr_ele;
double toDouble(char* str){
    double ans=0;
    int d=-1;
    int i=0;
    double p=1;
    for(i =0;str[i]!='\0';i++){
        if(str[i]=='.'){
            d = i;
            for(i++;str[i]!='\0';i++){
                p*=0.1;
                cout<<int(str[i]-'0')*p<<endl;
                ans+=1.0*(int(str[i]-'0'))*p;
            }
        }
    }
    p =1;
    if(d==-1){
        d = i;
    }
    for(int j=d-1;j>=0;j--){
        ans+=1.0*(int(str[j]-'0'))*p;
        p*=10;
    }
    return ans;

}

int getPri(char ch){
    if(ch == '+' || ch =='-'){
        return 1;
    }else if(ch == '*' || ch == '/'){
        return 2;
    }else if(ch =='('){
        return 3;
    }else
        return -1;
}

int main(int argc, const char * argv[]) {
    stack<expr_ele> s1;
    stack<expr_ele> s2;
    string str;
    char buffer[100];
    getline(cin,str);
    
    //中缀转后缀表达式
    for(int i =0;i<str.size();i++){
        if(str[i]<='9' && str[i]>='0'){
            int j =0;
            buffer[j++]=str[i++];
            buffer[j]='\0';
            while((str[i]<='9' && str[i]>='0') || str[i]=='.'){
                buffer[j++]=str[i++];
                buffer[j]='\0';
            }
            i--;
            expr_ele temp;
            temp.num = toDouble(buffer);
            temp.type= 0;
            s1.push(temp);
        }else if( '(' == str[i]){
            expr_ele temp;
            temp.op='(';
            temp.type=3;
            s2.push(temp);
        }else if( ')' == str[i]){
            expr_ele temp;
            temp = s2.top();
            while( '(' != temp.op){
                s1.push(temp);
                s2.pop();
                temp = s2.top();
            }
            s2.pop();
        }else{
            //cout<<str[i];
            while(1)
            if(s2.empty() || s2.top().op== '('){
                expr_ele temp;
                temp.op=str[i];
                temp.type=getPri(str[i]);
                s2.push(temp);
                break;
            }else{
                if( getPri(str[i]) > s2.top().type){
                    expr_ele temp;
                    temp.op=str[i];
                    temp.type=getPri(str[i]);
                    s2.push(temp);
                    break;
                }else{
                    expr_ele t = s2.top();
                    s1.push(t);
                    s2.pop();
                }
            }
        }
    }
    while(!s2.empty()){
        expr_ele temp = s2.top();
        s1.push(temp);
        s2.pop();
    }

    //逆序并输出
    vector<expr_ele> s;
    stack<expr_ele> s3;
    while(!s1.empty()){
        expr_ele temp = s1.top();
        s3.push(temp);
        s1.pop();
    }
    while(!s3.empty()){
        expr_ele temp = s3.top();
        s.push_back(temp);
        s3.pop();
    }

    for(int i=0;i<s.size();i++){
        if(s[i].type==0){
            cout<<s[i].num<<" ";
        }else{
            cout<<s[i].op<<" ";
        }
    }
    putchar(10);
    
    
    //运算
    stack<double>expr;
    for(int i=0;i<s.size();i++){
        if(s[i].type==0){
            expr.push(s[i].num);
        }else{
            double x,y,res;
            switch(s[i].op){
                case '+':
                    x = expr.top();expr.pop();
                    y = expr.top();expr.pop();
                    res = x+y;
                    expr.push(res);
                    break;
                case '-':
                    x = expr.top();expr.pop();
                    y = expr.top();expr.pop();
                    res = y-x;
                    expr.push(res);
                    break;
                case '*':
                    x = expr.top();expr.pop();
                    y = expr.top();expr.pop();
                    res = x*y;
                    expr.push(res);
                    break;
                case '/':
                    x = expr.top();expr.pop();
                    y = expr.top();expr.pop();
                    res = y/x;
                    expr.push(res);
                    break;
            }
        }
    }
    
    double ans = expr.top();
    cout<<ans<<endl;
    return 0;
}

添加新评论