中綴表示式就是我們通常所書寫的數學表示式，字尾表示式也稱為逆波蘭表示式，在編譯程式對我們書寫的程式中的表示式進行語法檢查時，往往就可以通過逆波蘭表示式進行。我們所要設計並實現的程式就是將中綴表示的算術表示式轉換成字尾表示，例如，將中綴表示式
(A 一 (B*C 十 D)*E) ／ (F 十 G )
轉換為字尾表示為：
ABC*D十E*--FG十／
注意：為了簡化程式設計實現，假定變數名均為單個字母，運運算元只有＋，－，＊，／ 和＾（指數運算），可以處理圓括號（），並假定輸入的算術表示式正確。
要求：使用棧資料結構實現 ，輸入的中綴表示式以＃號結束
整數N。表示下面有N箇中綴表示式
N個由單個字母、整數和運運算元構成的表示式
N個字尾表示式。
測試樣例1
1
(A-(B*C+D)*E)/(F+G)#
ABC*D+E*-FG+/
測試樣例2
2
a+b*c-d#
a-b*(c+d)#
abc*+d-
abcd+*-
#include <iostream>
#include <stack>
#include <string>
using namespace std;
stack <char> s;
int main()
{
//freopen("/Users/zhj/Downloads/test.txt","r",stdin);
int N;
cin >> N;
while (N--)
{
string in;
cin >> in;
int t = 0;
while (in[t] != '#')
{
if (t == 0 && in[t] == '-')
{//第一個數就是負數
cout << in[t];
}
else if (isalnum(in[t]))
{//如果是數位字母的話就輸出
cout << in[t];
}
else if (in[t] == '(')
{//是左括號的話就壓入棧中
s.push(in[t]);
}
else if (in[t] == ')')
{//如果是右括號的話，棧元素彈出，將彈出的操作符輸出直到遇到左括號為止
while(s.top()!='(')
{
cout<<s.top();
s.pop();
}
s.pop();
}
else if( in[t] =='-' && ( in[t - 1] == '(' || in[t - 1] == '*' || in[t - 1] == '/' || in[t - 1] == '%' || in[t - 1] == '+' || in[t - 1] == '-') )
{//此時是負數，且之前的是這些個符號的話，證明當前是一個負數
cout << in[t];
}
else
{//其他的操作符，從棧中彈出元素直到遇到發現更低優先順序的元素(或者棧為空)為止
if(s.empty())
{
s.push(in[t]);
}
else
{
int x, y;//x=ch,y=top of the stack
while (1)
{
if (s.empty())
{
s.push(in[t]);
break;
}
char chtmp = s.top();//chtmp此時是棧頂的元素
switch (in[t])
{//給此時的符號標記一個優先順序
case '^':{ x = 7; break;}
//10^2^2當然便是剛輸入這個^優先順序別更高，因為後面還可以繼續續上^2，變成10^2^2^2
case '*':{ x = 4; break;}
case '/':{ x = 4; break;}
case '+':{ x = 2; break;}
case '-':{ x = 2; break;}
}
switch (chtmp)
{//給之前的符號標記一個優先順序
case '^':{ y = 6; break;}
case '*':{ y = 5; break;}
case '/':{ y = 5; break;}
case '(':{ y = 1; break;}
case '+':{ y = 3; break;}
//如果之前是一個加號，此時的ch仍然是一個加號，那麼理應該輸出這個+號的，所以相應的之前的優先順序大一點
case '-':{ y = 3; break;}
}
if (y > x || y == x)
{//如果原來棧頂的優先順序大於之前的優先順序，那麼就輸出
cout<<chtmp;
s.pop();
continue;
}
else
{//不優先說明仍然在累計，則壓入棧中
s.push(in[t]);
break;
}
}
}
}
t++;
}
while (!s.empty())
{
cout<<s.top();
s.pop();
}
cout<<endl;
}
}
本題目主要的點也就是出現在對於負數的處理上面,以下給出一些樣例供參考
10
14*10-(10)*2#
14*10-(-10)*2#
14*10--10*2#
-14*-12#
-(1-2*-3)#
-3^-(1-2*-3)#
30/(-3+3)+1#
(-2)--3*(-8)#
-2--3*-8#
-A+B#