#include <iostream>
#include <cstdlib>
#include <string>
#include <stack>

using namespace std;

//棧內(nèi)符號(hào)優(yōu)先級(jí)
int is(const char c)
{
switch(c)
{
case '(': return 0;
case '+': return 2;
case '-': return 2;
case '*': return 4;
case '/': return 4;
case ')': return 5;
default: return -1;
}
}

//棧外符號(hào)優(yōu)先級(jí)
int os(const char c)
{
switch(c)
{
case '(': return 6;
case '+': return 1;
case '-': return 1;
case '*': return 3;
case '/': return 3;
case ')': return 0;
default: return -1;
}
}

//四元式翻譯
int translate1(string s)
{
stack<string> OPND;
stack<char> OPER;
char op;
string left, right;
int step = 0;
char sChange[10];
string sTemp;

cout << "轉(zhuǎn)換成四元式:" << endl;

for (int i=0; i<(int)s.length(); i++)
{
   if ( (s[i]>='0' && s[i]<='9') || (s[i]>='a' && s[i]<='z') )
   {
    sTemp = "";
    sTemp += s[i];
    OPND.push(sTemp);
   }
   else
   {
    while (!OPER.empty() && os(s[i])<is(OPER.top()))
    {
     right = OPND.top();
     OPND.pop();
     left = OPND.top();
     OPND.pop();
     op = OPER.top();
     OPER.pop();
     cout << "(" << step << ")   ";
     step++;
     sTemp = _itoa(step, sChange, 10);
     sTemp = "T" + sTemp;
     OPND.push(sTemp);
     cout << op << "   " << left << "   " << right << "   " << sTemp << endl;
    }
    if(!OPER.empty() && os(s[i])==is(OPER.top()))
     OPER.pop();
    else
     OPER.push(s[i]);
   }
}
while (!OPER.empty())
{
   right = OPND.top();
   OPND.pop();
   left = OPND.top();
   OPND.pop();
   op = OPER.top();
   OPER.pop();
   cout << "(" << step << ")   ";
   step++;
   sTemp = _itoa(step, sChange, 10);
   sTemp = "T" + sTemp;
   OPND.push(sTemp);
   cout << op << "   " << left << "   " << right << "   " << sTemp << endl;
}
return 0;
}

int main()
{
string s;
while (true)
{
   cout << "請(qǐng)輸入一個(gè)算術(shù)表達(dá)式：" << endl;
   cin >> s;
   translate1(s);
   cout << endl;
  }
return 0;
}