簡單電腦求值（中綴表達式轉化成字尾表達式）

題目連結：http://hihocoder.com/contest/hiho169/problem/1

題目解答：

輸入表達式之後，轉化成字尾表達式（逆波蘭表達式）

中綴表達式轉字尾表達式的方法：

1.遇到操作數：直接輸出（添加到字尾表達式中）

2.棧為空時，遇到運算符，直接入棧

3.遇到左括号：将其入棧

4.遇到右括号：執行出棧操作，并将出棧的元素輸出，直到彈出棧的是左括号，左括号不輸出。

5.遇到其他運算符：加減乘除：彈出所有優先級大于或者等于該運算符的棧頂元素，然後将該運算符入棧

6.最終将棧中的元素依次出棧，輸出。

例如

a+b*c+(d*e+f)g —-> abc+de*f+g*+

遇到a:直接輸出：

字尾表達式：a

堆棧：空

遇到+:堆棧：空，是以+入棧

字尾表達式：a

堆棧：+

遇到b: 直接輸出

字尾表達式：ab

堆棧：+

遇到：堆棧非空，但是+的優先級不高于，是以*入棧

字尾表達式： ab

堆棧：*+

遇到c:直接輸出

字尾表達式：abc

堆棧：*+

遇到+：堆棧非空,堆棧中的*優先級大于+，輸出并出棧，堆棧中的+優先級等于+，輸出并出棧，然後再将該運算符(+)入棧

字尾表達式：abc*+

堆棧：+

遇到(：直接入棧

字尾表達式：abc*+

堆棧：(+

遇到d：輸出

字尾表達式：abc*+d

堆棧：(+

遇到：堆棧非空，堆棧中的(優先級小于，是以不出棧

字尾表達式：abc*+d

堆棧：*(+

遇到e：輸出

字尾表達式：abc*+de

堆棧：*(+

遇到+：由于的優先級大于+，輸出并出棧，但是(的優先級低于+，是以将出棧，+入棧

字尾表達式：abc*+de*

堆棧：+(+

遇到f：輸出

字尾表達式：abc*+de*f

堆棧：+(+

遇到)：執行出棧并輸出元素，直到彈出左括号，所括号不輸出

字尾表達式：abc*+de*f+

堆棧：+

遇到*：堆棧為空，入棧

字尾表達式： abc*+de*f+

堆棧：*+

遇到g：輸出

字尾表達式：abc*+de*f+g

堆棧：*+

遇到中綴表達式結束：彈出所有的運算符并輸出

字尾表達式：abc*+de*f+g*+

堆棧：空

字尾表達式算法

設定一個棧，開始時，棧為空，然後從左到右掃描字尾表達式，若遇操作數，則進棧；若遇運算符，則從棧中退出兩個元素，先退出的放到運算符的右邊，後退出的 放到運算符左邊，運算後的結果再進棧，直到字尾表達式掃描完畢。此時，棧中僅有一個元素，即為運算的結果。

#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<list>
#include<deque>
using namespace std;
typedef long long ll;
const int maxn =  + ;
const double eps = ;
const int INF =  << ;
int T, n, m;
int q[];
map<char, int>Map;
void init()
{
    Map['+'] = ;
    Map['-'] = ;
    Map['*'] = ;
    Map['/'] = ;
    Map['('] = ;
}
void solve (string s, string& ans, int & sum)
{
    ans = "";
    int num = , tot = ;
    for(int i = ; i < s.size(); i++)
    {
        if(isdigit(s[i]))num++;
        else if(num)q[tot++] = num, num = ;
    }
    if(num)q[tot++] = num;
    stack<char>sign;
    char c;
    for(int i = ; i < s.size(); i++)
    {
        if(isdigit(s[i]))ans += s[i];
        else
        {
            if(sign.empty() || s[i] == '(')sign.push(s[i]);
            else
            {
                if(s[i] == ')')
                {
                    while()
                    {
                        c = sign.top();
                        sign.pop();
                        if(c == '(')break;
                        ans += c;
                    }
                }
                else
                {
                    while()
                    {
                        if(sign.empty())
                        {
                            sign.push(s[i]);
                            break;
                        }
                        c = sign.top();
                        if(Map[c] < Map[s[i]])
                        {
                            sign.push(s[i]);
                            break;
                        }
                        else
                        {
                            ans += c;
                            sign.pop();
                        }
                        //cout<<"c::"<<c<<endl;
                    }
                }
            }
        }
    }
    while(!sign.empty())ans += sign.top(),sign.pop();
   // cout<<ans<<endl;
    stack<int>took;  // cout<<ans<<"   "<<ans2<<endl;
    tot = num = ;
    int a, b;
    for(int i = ; i < ans.size(); i++)
    {
        if(isdigit(ans[i]))
        {
            for(int j = i; j < i + q[tot]; j++)
            {
                num = num *  + ans[j] - '0';
            }
            i = i + q[tot++] - ;
            took.push(num);
            //cout<<num<<endl;
            num = ;
        }
        else
        {
            a = took.top();
            //cout<<"a"<<a<<endl;
            took.pop();
            b = took.top();
            //cout<<"b"<<b<<endl;
            took.pop();
            if(ans[i] == '*')took.push(a * b);
            if(ans[i] == '+')took.push(a + b);
            if(ans[i] == '-')took.push(b - a);
            if(ans[i] == '/')took.push(b / a);
        }
    }
   sum = took.top();
}
int main()
{
    string s, ans;
    int num;
    init();
    while(cin >> s)
    {
        solve(s, ans, num);
        cout<<num<<endl;
    }
    return ;
}