C++四則演算コード

問題の概要
プログラミングは文字列形式を直接解く4つの演算式を実現するアルゴリズム問題であり,この問題は乗算除算演算と括弧演算を加えるにつれて難易度が増加する.
問題の解決には、次の3つのステップが必要です.

入力された式、すなわち、一般的に見られる式を接尾辞式と呼び、接尾辞式に変換します.

は、スタックデータ構造を用いて接尾辞式を直接使用して、4つの演算式の計算を実現する.

具体的なコードは、まず接尾辞式をvectorコンテナに適切に分割し、その後、コンテナ内の要素を一定のアルゴリズムに従って接尾辞式に変換し、最後に接尾辞式を解く.

最後のコードはこれらのステップを一定に分割し,すなわちC++プログラミングを用いたが,基本的にはプロセス向けのC言語の形式でプログラミングを行った.
部分アルゴリズムの説明
最も面倒な部分アルゴリズムは、接尾辞式を接尾辞式アルゴリズムに変換することです.具体的な手順は次のとおりです.

遭遇オペランド:直接出力(接尾辞式に追加)

スタックが空の場合、演算子に遭遇し、直接スタック

に入る

左かっこ:スタック

に挿入

は右かっこに遭遇しました.スタックを出る操作を実行し、スタックの要素をポップアップスタックが左かっこになるまで出力します.左かっこは出力しません.

他の演算子に遭遇した:加算減算:演算子以上の優先度を持つすべてのスタックトップ要素をポップアップし、その演算子をスタック

に入力します.

は、最終的にスタック内の要素を順次スタックから出力する.

接尾辞式の計算アルゴリズム

式の各数値および記号の左から右への遍歴

数字に出会ったらスタック

に入る

シンボルに遭遇すると、スタックの一番上の2つの要素をスタック(最初のスタックはオペランドB、2番目のスタックはオペランドA)

に出力する.

その後、演算AオペレータBを行い、計算結果をスタック

に入力する.

最終結果が得られるまで.

実装コードで使用されるいくつかの補助コード

boostライブラリで提供されるデータ型変換関数-lexical_を使用castは,もちろんコードにも機能がほぼ同等であるSTLフロー操作を用いて実現されるデータ型変換が用いられており,その性能の違いについてはさらに深く研究されていない.

は、STLに提供されるvector線形コンテナ、および対応するスタックデータ構造stackをより多く使用する.プログラマーの先輩は、すでに車輪があれば、この車輪があることを知らない限り、車輪を繰り返し発明する必要はないと言っています.

完全なコード

#include 
#include 
#include 
#include 
#include 

using namespace std;
using namespace boost;

/*
 ConvertDataType: This function can convert data type from in to out. This
    function has the same function as lexical_cast function, So this function can
    replace the function provided by lexical_cast.
 */
template<class out, class in>
out ConvertDataType(const in& a)
{
    std::stringstream temp;
    temp << a;
    out b;
    temp >> b;
    return b;
}

/*
 isOper: This function used to check whether oper is +, -, *, /, (, )
    The other isOper function is overload function for same use.
 */
bool isOper(string oper);
bool isOper(char oper);
/*
 getPriority: This function used to get priority of math operator which will
     used in converting Prefix Expression To Postfix Expression.
     The other same name function is a ovlerload function for same function.
 */
int getPriority(char oper);
int getPriority(string oper);
/*
 doMath: This function used to real calculate of add sub multiply and divide.
    The other same name function is a ovlerload function for same function.
 */
double doMath(double operOne, double operTwo, char oper);
double doMath(double operOne, double operTwo, string oper);
/*
 splitPrefixExpression: split the string to vector whic contains every element of equaltion
    in same order, like 9+(3-1)*3+10/2 -> 9, +, (, 3, -, 1, ), *, 3, +, 10, /, 2
 */
vector<string> splitPrefixExpression(string prefixExpression);
/*
 convertPrefixExpressionToPostfixExpression: convert Prefix Expression To Postfix Expression.
 */
vector<string> convertPrefixExpressionToPostfixExpression(vector<string> prefixExpression);
/*
 calculatePostfixExpression: calculate Postfix Expression.
 */
double calculatePostfixExpression(vector<string> postfixExpression);

bool isOper(string oper) {
    if (1 == oper.size()) {
        return isOper(oper[0]);
    }
    return false;
}

bool isOper(char oper) {
    return ('+' == oper || '-' == oper || '*' == oper ||
            '/' == oper || '(' == oper || ')' == oper )? true : false;
}

int getPriority(char oper) {
    switch (oper) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
        case ')':
            return 0;
        default:
            return -1;
    }
}

int getPriority(string oper) {
    if (1 == oper.size()) {
        return getPriority(oper[0]);
    }
    return -1;
}

double doMath(double operOne, double operTwo, char oper) {
    switch(oper){
        case '+':
            return operOne + operTwo;
        case '-':
            return operOne - operTwo;
        case '*':
            return operOne * operTwo;
        case '/':
            return operOne / operTwo;
        default:
            return 0.0f;
    }
}

double doMath(double operOne, double operTwo, string oper) {
    if (1 == oper.size()) {
        return doMath(operOne, operTwo, oper[0]);
    }
    return 0.0f;
}

vector<string> splitPrefixExpression(string prefixExpression) {
    vector<string> result;
    int tempIndex = 0;
    for (int index = 0; index < prefixExpression.size(); index++) {
        /*below statements of if is to get the operator in the equaltion*/
        if (isOper(prefixExpression[index])) {
            result.push_back(prefixExpression.substr(index, 1));
            continue;
        }
        /*filter away the spaces which may be exist in equaltion*/
        if (' ' == prefixExpression[index]) {
            continue;
        }
        /*below while statements which will get numbers(maybe more than one bits 
         or may have dot in that(float))*/
        tempIndex = index;
        while (prefixExpression[index] >= '0' && prefixExpression[index] <= '9') {
            if (' ' == prefixExpression[index + 1] || isOper(prefixExpression[index + 1]) ||
                index == prefixExpression.size() - 1) {
                result.push_back(prefixExpression.substr(tempIndex, index - tempIndex + 1));
                //index--;
                break;
            }
            index++;
        }
    }
    return result;
}
/*
               ：
 1.     ：    （         ）
 2.    ，     ，    
 3.     ：    
 4.     ：      ，         ，          ，      。
 5.       ：    ：                      ，         
 6.            ，  。
 */
vector<string> convertPrefixExpressionToPostfixExpression(vector<string> prefixExpression) {
    vector<string> result;
    stack<string> tool;
    for (auto const& item : prefixExpression) {
        if (isOper(item)) {
            if (tool.empty() || "(" == item) {
                tool.push(item);
            } else if (")" == item) {
                while ("(" != tool.top()) {
                    result.push_back(tool.top());
                    tool.pop();
                }
                tool.pop();
            } else {
                while (!tool.empty() && (getPriority(item) <= getPriority(tool.top()))) {
                    result.push_back(tool.top());
                    tool.pop();
                }
                tool.push(item);
            }
        } else {
            result.push_back(item);
        }
    }
    while (!tool.empty()){
        result.push_back(tool.top());
        tool.pop();
    }
    return result;
}
/*
                  ，       ，               (      
     B，           A),     A     B，        ，         。
 */
double calculatePostfixExpression(vector<string> postfixExpression) {
    stack<double> tool;
    double operOne = 0.0f;
    double operTwo = 0.0f;
    for (auto const & item : postfixExpression) {
        if (!isOper(item)){
            /*
             below two line code implements same function with different function.
             */
            //tool.push(lexical_cast(item));
            tool.push(ConvertDataType<double>(item));
        } else {
            operTwo = tool.top();
            tool.pop();
            operOne = tool.top();
            tool.pop();
            tool.push(doMath(operOne, operTwo, item));
        }
    }
    return tool.top();
}

int main() {
    string expression = "9 + 6*(3 - (3 + 9) *1) * 3 + 10 / 2";
    cout << calculatePostfixExpression(convertPrefixExpressionToPostfixExpression(splitPrefixExpression(expression))) << endl;
    return 0;
}