寫(xiě)在前面，這里用的是我自己寫(xiě)的Stack類(lèi)，并非STL，實(shí)現(xiàn)方法為靜態(tài)數(shù)組，但使用過(guò)程中的函數(shù)方法一樣，無(wú)傷大雅。（完整code和Stack_static類(lèi)賦在最后）
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式：
1.從左到右遍歷
2.數(shù)，即參與運(yùn)算數(shù)，直接放進(jìn)后綴表達(dá)式之后
3.左括號(hào)，直接壓入棧（因?yàn)槔ㄌ?hào)的優(yōu)先級(jí)最高，無(wú)需判斷）（入棧后優(yōu)先級(jí)最低，確保其它的符號(hào)正常入棧）
4.右括號(hào),意味著括號(hào)已經(jīng)結(jié)束，那么不斷彈出棧頂，直到遇到左括號(hào)。
5.運(yùn)算符,將該運(yùn)算符與棧頂運(yùn)算符進(jìn)行比較
????????如果優(yōu)先級(jí)高于棧頂運(yùn)算符則壓入堆棧
????????如果優(yōu)先級(jí)低于或等于棧頂運(yùn)算符則將棧頂運(yùn)算符彈出并放入后綴表達(dá)式中
????????***這里是核心，低于或等于棧頂元素意味著前面部分可以運(yùn)算了，先放入表達(dá)式，即先進(jìn)行運(yùn)算的一定是高優(yōu)先級(jí)的運(yùn)算符。
????????直到優(yōu)先級(jí)大于棧頂運(yùn)算符或者棧空，再將該運(yùn)算符入棧。
6.對(duì)字符串處理完畢后，則按順序彈出棧中所剩運(yùn)算符，放入表達(dá)式中
這里我給出一個(gè)例子：2+(3*(4-1))+3
code中的棧類(lèi)是我自己寫(xiě)的類(lèi)，不是STL中的，但功能大致一樣，
/*
返回運(yùn)算符的優(yōu)先級(jí)
*/
int value(char c){
switch(c){
case '(':
return 0;
break;
case '+':
case '-':
return 1;
break;
case '*':
case '/':
return 2;
break;
default:
cout<<"input error"<<endl;
return 0;
}
}
//將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式
string change(string str){
string changed = "";
Stack_static s;
int opflag = 1;//記錄運(yùn)算符是否出現(xiàn)，用于判斷-是負(fù)號(hào)還是減號(hào)。
for(int i = 0; i < int(str.length());i++){
if(str[i]>='0' && str[i]<='9'){//若為數(shù)字，則直接接到后綴表達(dá)式后面
changed += str[i];
opflag = 0;
}
else if(str[i]=='('){//若為左括號(hào)，直接壓入棧
s.push(str[i]);
}
else if(str[i]==')'){//若為右括號(hào)，一直出棧接入后綴表達(dá)式，直到遇到左括號(hào)
while(s.top()!='('){
changed += ' ';
changed += s.top();
s.pop();
if(s.empty())break;
}
s.pop();
}
else{
if(opflag){
changed += str[i];
opflag = 0;
}
else{
changed += ' ';//遇到正常的符號(hào)，說(shuō)明一個(gè)數(shù)字已經(jīng)輸入完畢，所以加一個(gè)空格隔開(kāi)個(gè)個(gè)數(shù)字
if(s.empty())s.push(str[i]);//若?？?，則直接入棧
else if(value(str[i]) > value(s.top()))s.push(str[i]);//若優(yōu)先級(jí)大于棧頂，直接入棧
else {//若優(yōu)先級(jí)小于等于前一個(gè)，則不斷比較并出棧
while(value(str[i]) <= value(s.top())){
changed += s.top();
changed += ' ';
s.pop();
if(s.empty())break;//如果空了，退出循環(huán)
}
s.push(str[i]);
}
opflag = 1;
}
}
}
while(!s.empty()){//當(dāng)結(jié)束時(shí)，棧不為空，則一個(gè)一個(gè)出棧
changed += ' ';
changed += s.top();
s.pop();
}
return changed;//返回最終的后綴表達(dá)式
}接下來(lái)是后綴表達(dá)式的求值方法
1.依舊是從左到右遍歷字符串
2.數(shù)，這次的數(shù)的處理是直接壓入棧
3.符號(hào)，若是空格，則將前面保存的數(shù)壓入棧（因?yàn)閿?shù)可能是多位數(shù)，所以不能直接壓入棧，有別于轉(zhuǎn)后綴。所以我們需要一個(gè)數(shù)來(lái)保存字符輸進(jìn)來(lái)的數(shù)字。）
4.運(yùn)算符，碰到一個(gè)運(yùn)算符，我們就進(jìn)行一次計(jì)算，對(duì)棧頂?shù)膬蓚€(gè)數(shù)字進(jìn)行計(jì)算，這也就是后綴表達(dá)式的計(jì)算原理
接下來(lái)舉個(gè)例子，式子與上面的相同
后綴表達(dá)式為2 3 4 1-* 3++
最后所剩的14即為最終答案，直接輸出即可
下面是實(shí)現(xiàn)的代碼
//計(jì)算兩個(gè)數(shù)，用于彈出的運(yùn)算符和兩個(gè)數(shù)
double calculate(double x,double y,char c){
switch (c)
{
case '+':
return x+y;
break;
case '-':
return x-y;
break;
case '*':
return x*y;
break;
case '/':
if(!y){
cerr<<"除數(shù)不能為0"<<endl;
exit(0);
}
return x/y;
break;
default:
cerr<<"input error"<<endl;
exit(0);
break;
}
}
//計(jì)算后綴表達(dá)式的值
double result(string str){
Stack_static S_num;
int num = 0,flag = 0,fu_flag = 0;
for(int i = 0;i < int(str.length());i++){
if(str[i]>='0' && str[i]<='9'){//遇到數(shù)字存入num中
num = num*10 + str[i]-'0';
flag = 1;//flag用來(lái)記錄現(xiàn)在數(shù)字是否存在
}
else{
if(flag){//避免連續(xù)讀入字符時(shí)，數(shù)字棧中存入多個(gè)0
if(fu_flag)//如果是負(fù)數(shù)
S_num.push(-double(num));
else
S_num.push(double(num));
flag = 0;
fu_flag = 0;
num = 0;//置0
}
if(str[i]==' '){
fu_flag = 0;
continue;
}
if(str[i]=='-' && str[i+1]>='0' && str[i+1]<='9'){
fu_flag = 1;
continue;
}
double a,b;
a = S_num.top();//取出棧頂
S_num.pop();
b = S_num.top();//取出棧頂
S_num.pop();
S_num.push(calculate(b,a,str[i]));//計(jì)算后壓入棧
}
}
return S_num.top();
}我的Stack_static類(lèi)，是靜態(tài)數(shù)組的實(shí)現(xiàn)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-434920.html
#include<iostream>
const int STACK_MAX = 128;
typedef int StackElement;
class Stack_static
{
private:
StackElement myArray[STACK_MAX];
int myTop;
public:
Stack_static();
~Stack_static();
void push(const StackElement &value);
void pop();
StackElement top();
bool empty();
void display(std::ostream & out);
int get_myTop(){
return myTop;
}
StackElement bottom();
};
Stack_static::Stack_static()
{
myTop = -1;
}
Stack_static::~Stack_static()
{
}
bool Stack_static::empty(){
if(myTop==-1)return true;
return false;
}
StackElement Stack_static::top(){
if( !empty())
return myArray[myTop];
else{
std::cerr << "*** Stack is empty -- return ***\n";
StackElement garbage=0;
return garbage;
}
}
void Stack_static::push(const StackElement &value){
if(myTop < STACK_MAX-1){
myTop++;
myArray[myTop] = value;
}
else{
std::cerr << "*** Stack full -- can't add new value ***\n";
exit(1);
}
}
void Stack_static::pop(){
if(!empty())
myTop--;
else
std::cerr << "*** Stack is empty***\n";
}
void Stack_static::display(std::ostream &out){
for(int i = myTop-1;i >= 0; i-- ){
out<< myArray[i] << std::endl;
}
}
StackElement Stack_static::bottom(){
if(!empty()){
return myArray[0];
}
else{
std::cerr<<"*** Stack is empty!***\n";
StackElement garbage=0;
return garbage;
}
}整個(gè)代碼以及測(cè)試：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-434920.html
#include"Stack_static.h"
#include<iostream>
using namespace std;
//簡(jiǎn)易計(jì)算器，只包含+-*/（）
/*
返回運(yùn)算符的優(yōu)先級(jí)
*/
int value(char c){
switch(c){
case '(':
return 0;
break;
case '+':
case '-':
return 1;
break;
case '*':
case '/':
return 2;
break;
default:
cout<<"input error"<<endl;
return 0;
}
}
//計(jì)算兩個(gè)數(shù)，用于彈出的運(yùn)算符和兩個(gè)數(shù)
double calculate(double x,double y,char c){
switch (c)
{
case '+':
return x+y;
break;
case '-':
return x-y;
break;
case '*':
return x*y;
break;
case '/':
if(!y){
cerr<<"除數(shù)不能為0"<<endl;
exit(0);
}
return x/y;
break;
default:
cerr<<"input error"<<endl;
exit(0);
break;
}
}
//將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式
string change(string str){
string changed = "";
Stack_static s;
int opflag = 1;//記錄運(yùn)算符是否出現(xiàn)，用于判斷-是負(fù)號(hào)還是減號(hào)。
for(int i = 0; i < int(str.length());i++){
if(str[i]>='0' && str[i]<='9'){//若為數(shù)字，則直接接到后綴表達(dá)式后面
changed += str[i];
opflag = 0;
}
else if(str[i]=='('){//若為左括號(hào)，直接壓入棧
s.push(str[i]);
}
else if(str[i]==')'){//若為右括號(hào)，一直出棧接入后綴表達(dá)式，直到遇到左括號(hào)
while(s.top()!='('){
changed += ' ';
changed += s.top();
s.pop();
if(s.empty())break;
}
s.pop();
}
else{
if(opflag){
changed += str[i];
opflag = 0;
}
else{
changed += ' ';//遇到正常的符號(hào)，說(shuō)明一個(gè)數(shù)字已經(jīng)輸入完畢，所以加一個(gè)空格隔開(kāi)個(gè)個(gè)數(shù)字
if(s.empty())s.push(str[i]);//若?？眨瑒t直接入棧
else if(value(str[i]) > value(s.top()))s.push(str[i]);//若優(yōu)先級(jí)大于棧頂，直接入棧
else {//若優(yōu)先級(jí)小于等于前一個(gè)，則不斷比較并出棧
while(value(str[i]) <= value(s.top())){
changed += s.top();
changed += ' ';
s.pop();
if(s.empty())break;//如果空了，退出循環(huán)
}
s.push(str[i]);
}
opflag = 1;
}
}
}
while(!s.empty()){//當(dāng)結(jié)束時(shí)，棧不為空，則一個(gè)一個(gè)出棧
changed += ' ';
changed += s.top();
s.pop();
}
return changed;//返回最終的后綴表達(dá)式
}
//計(jì)算后綴表達(dá)式的值
double result(string str){
Stack_static S_num;
int num = 0,flag = 0,fu_flag = 0;
for(int i = 0;i < int(str.length());i++){
if(str[i]>='0' && str[i]<='9'){//遇到數(shù)字存入num中
num = num*10 + str[i]-'0';
flag = 1;//flag用來(lái)記錄現(xiàn)在數(shù)字是否存在
}
else{
if(flag){//避免連續(xù)讀入字符時(shí)，數(shù)字棧中存入多個(gè)0
if(fu_flag)//如果是負(fù)數(shù)
S_num.push(-double(num));
else
S_num.push(double(num));
flag = 0;
fu_flag = 0;
num = 0;//置0
}
if(str[i]==' '){
fu_flag = 0;
continue;
}
if(str[i]=='-' && str[i+1]>='0' && str[i+1]<='9'){
fu_flag = 1;
continue;
}
double a,b;
a = S_num.top();//取出棧頂
S_num.pop();
b = S_num.top();//取出棧頂
S_num.pop();
S_num.push(calculate(b,a,str[i]));//計(jì)算后壓入棧
}
}
return S_num.top();
}
//測(cè)試代碼
int main(){
string a;
cout << "Infix expression?";
cin >> a;
cout << "Postfix expression is " << change(a) << endl;
cout << "Result:" << result(change(a));
return 0;
}到了這里，關(guān)于C++ 數(shù)據(jù)結(jié)構(gòu) 棧 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式并求值的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
