ReZero's Utopia.

求后缀表达式

字数统计: 675阅读时长: 3 min
2016/11/02 Share

这个题网上各种乱七八糟的代码
这里对方法总结一下
把代码写得稍微能看一点
~个屁啊。。。。 最叼解释大神不过一句话带过

规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

//中缀表达式转后缀表达式的方法:
//1.遇到操作数:直接输出(添加到后缀表达式中)
//2.栈为空时,遇到运算符,直接入栈
//3.遇到左括号:将其入栈
//4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。
//5.遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈
//6.最终将栈中的元素依次出栈,输出。
//fork from http://www.cnblogs.com/mygmh/archive/2012/10/06/2713362.html

#include <iostream>
#include <map>
#include <stack>
#include <cstdio>
using namespace std;

map<char, int> sym;
void init(){
    sym.insert(make_pair('+',1));
    sym.insert(make_pair('-',1));
    sym.insert(make_pair('*',2));
    sym.insert(make_pair('/',2));
}

bool isInt(char c){
    return (c >= '0' && c <= '9');
}

double calc(double a, double b, char c){
    if(c == '+') return a+b;
    else if(c == '-') return b-a;
    else if(c == '*') return b*a;
    return b/a;

}

int main(){
    string ss;
    init();
    int kase = 1;
    while(cin >> ss){
        cout << "Case #" << kase++ << ":"  << endl;
        stack<char> last;
        stack<double> answer;
        int qsize = ss.size();

        for(int i = 0; i < qsize; ++i){
            if(isInt(ss[i])){ /// num is the true num
                double num = 0;
                while(isInt(ss[i])){
                    num = num * 10 + ss[i] - '0';
                    ++i;
                }
                int point = 0;
                if(ss[i] == '.') {
                    ++i;

                    while(isInt(ss[i])){
                        num = num * 10 + ss[i] - '0';
                        ++i;    ++point;
                    }
                    --i;
                    for(int j = 0; j < point; ++j){
                        num /= 10.0;
                    }

                } else --i;
                printf("%.*lf ", point, num);
                answer.push(num);

            }
            else if (last.empty() || ss[i] == '('){
                last.push(ss[i]);
            }
            else if(ss[i] == ')') {
                while(last.top() != '('){
                        ///calculate the num
                        double a = answer.top(); answer.pop();
                        double b = answer.top(); answer.pop();
                        answer.push(calc(a,b, last.top()));


                        ///epichar
                    cout << last.top();
                    last.pop();
                }
                last.pop();
            }
            else{
                while(!last.empty() && sym[ss[i]] <= sym[last.top()]){
                    double a = answer.top(); answer.pop();
                    double b = answer.top(); answer.pop();
                    answer.push(calc(a,b, last.top()));

                    cout << last.top();
                    last.pop();
                }
                last.push(ss[i]);
            }
        }
        while(!last.empty()) {
            double a = answer.top(); answer.pop();
            double b = answer.top(); answer.pop();
            answer.push(calc(a,b, last.top()));

            cout << last.top();
            last.pop();
        }
        cout << endl;
        cout << "The answer is ";
        double ans = answer.top();
        printf("%g",ans);
        cout << "." <<endl << endl;
    }


}

/**************************************************************
    Problem: 1684
    User: 201501060807
    Language: C++
    Result: Accepted
    Time:1668 ms
    Memory:1296 kb
****************************************************************/
CATALOG