本題是求算數表達式的值。操作數是大於等於的實數，操作符有 + ,- ,*,/,() 只要開兩個棧，一個記錄操作符，一個記錄後綴表達式。 即:把原始的中綴表達式轉換成後綴表達式（逆波蘭式），然後進行計算。 前綴和後綴表示法有三項公共特征： 操作數的順序與等價的中綴表達式中操作數的順序一致 不需要括號 操作符的優先級不相關 中綴轉化為後綴算法： a. 得到一操作符或操作數； b. 若輸入為操作數，則輸出到數組,轉a; c. 若輸入為‘（’，壓棧,轉a； d. 若輸入為‘）’，棧頂出棧，輸出到數組，直至棧頂為‘（’，不輸出到數組（拋棄），轉a; e. 若輸入為操作符， 若棧空或棧頂為‘（’或操作符.憂先級大於棧頂操作符，壓棧,轉a 若操作符優先級小於棧頂操作符，則出棧，輸出至數組，轉e； d. 若輸入結束，出棧，輸出到數組，直至棧空。 [cpp] #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <algorithm> #include <stack> #include <queue> #include <map> #include <string> using namespace std; int priority[100]; //初始化操作符優先級 void initPri() { priority['('] = 1; priority['+'] = 2; priority['-'] = 2; priority['*'] = 3; priority['/'] = 3; } //a是符號棧頂，b是當前判斷符號 //a>=b，返回true;a<b,返回false bool judgeOpePri(char a,char b) { return priority[a] >= priority[b] ? true : false; } //兩個參數：中綴表達式，生成的後綴表達式 void convert(string infixExp,stack<string> &postfixExp) { //運算符棧 stack<char> opS; //臨時操作數 string digitTemp; //臨時操作符 string operTemp; int len = infixExp.length(); bool hasDigit = false; //過濾掉'=' for(int i=0; i<len-1;) { //如果是操作數的一部分 while((isdigit(infixExp[i]) || infixExp[i] == '.') && i<len-1) { hasDigit = true; digitTemp.push_back(infixExp[i]); i++; } if(hasDigit == true) { postfixExp.push(digitTemp); digitTemp = ""; hasDigit = false; } else { //如果操作符棧是空的，就入棧 if(opS.empty()) { opS.push(infixExp[i]); i++; } //注意對於'('同等優先級是不起作用的 else if(infixExp[i] == '(') { opS.push(infixExp[i]); i++; } //彈出"()"之內的所有運算符 else if(infixExp[i] == ')') { while(!opS.empty()) { char c = opS.top(); operTemp = ""; operTemp.push_back(c); opS.pop(); if(c == '(') { break; } else { postfixExp.push(operTemp); } } i++; } //操作符棧頂的優先級大 else if(judgeOpePri(opS.top(),infixExp[i]) == true) { char c = opS.top(); operTemp = ""; operTemp.push_back(c); opS.pop(); postfixExp.push(operTemp); //注意此時不要i++,因為還要繼續比較 } //操作符棧頂的優先級小 else { opS.push(infixExp[i]); i++; } } } //清空符號棧 while(!opS.empty()) { char c = opS.top(); operTemp = ""; operTemp.push_back(c); opS.pop(); postfixExp.push(operTemp); } } double answerQ(stack<string> &postfixExp) { stack<string> couterFix; stack<double> resultSta; while(!postfixExp.empty()) { couterFix.push(postfixExp.top()); postfixExp.pop(); } double a,b; while(!couterFix.empty()) { string c = couterFix.top(); double d; couterFix.pop(); int cas = 5; if(strcmp(c.c_str(),"+") == 0) cas = 0; else if(strcmp(c.c_str(),"-") == 0) cas = 1; else if(strcmp(c.c_str(),"*") == 0) cas = 2; else if(strcmp(c.c_str(),"/") == 0) cas = 3; if(cas!=5) { double a = resultSta.top(); resultSta.pop(); double b = resultSta.top(); resultSta.pop(); switch(cas) { case 0: { resultSta.push(b + a); break; } case 1: { resultSta.push(b - a); break; } case 2: { resultSta.push(b * a); break; } case 3: { resultSta.push(b / a); break; } default: {} } } else { sscanf(c.c_str(),"%lf",&d); resultSta.push(d); } } return resultSta.top(); } int main() { /*#ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif*/ int n; scanf(" %d",&n); initPri(); while(n--) { string infixExp; stack<string> postfixExp; cin>>infixExp; convert(infixExp,postfixExp); double ans = answerQ(postfixExp); printf("%.2lf\n",ans); } return 0; }
