栈实现中缀表达式转换成后缀表达式并计算

╰+哭是因爲堅強的太久メ 2022-05-28 09:23 165阅读 0赞

![这里写图片描述][70]

#include <iostream>
    // cin 为输入 cout 为输出 
    #include <cstring>
    // 用栈 来 处理 一般的 中缀计算表达式
    // 这里 只实现了 最基本的 + - * / 也可以根据程序需要 添加 ^ 和 % 以及 开方等运算 
    using namespace std; 
    int campareToChar(char ch){
       // 判断 字符的优先级 
        switch(ch){
            case '+':
            case '-':return 1;
            case '*':
            case '/':return 2; // * / 的优先级高 
            default: return -1; 
        } 
    }  
    double createToNum(char stack[], int len);// 将 转换的后缀表达式 计算出来 
    
    int main(int argc, char** argv) {
        char cinStr[1000] = {
       '\0'};         // 存储输入 进来的字符串 
        char stackS1[1000] = {
       '\0'};        // 保存 后缀表达式 
        char tempS2[1000] = {
       '\0'};         // 临时 保存运算符 -- 看代码这里的变量的用处要记一下 
        int topS1 = 0;
        int topS2 = 0;
        double num[1000];
        cout << "输入要计算的式子: " << endl; 
        cin >> cinStr;  // 输入字符串 
        fflush(stdin);
    
        int i = 0;
        while(cinStr[i] != '\0'){                       // 转换成后缀表达式 
    
            if(cinStr[i] == '('){                       // 遇到左括号 直接进到后缀表达式
                tempS2[topS2++] = cinStr[i]; 
    
            }else if(cinStr[i] == ')'){                 // 遇到右括号就 开始 查找左括号 
                while(tempS2[topS2 - 1] != '('){
                    stackS1[topS1++] = tempS2[--topS2]; // 将 所有'('前的 运算符全部弹出到后缀表达式
                } 
                topS2--;                                // 丢弃'(' 
    
            }else if(cinStr[i] >= '0' && cinStr[i] <= '9' || cinStr[i] == '.'){
       // 数字和 . 直接进到后缀表达式
                stackS1[topS1++] = cinStr[i];
    
            }else{                                      // 处理运算符 
                stackS1[topS1++] = ' ';
                if(topS2 == 0){                         // 如果栈里面没有 运算符符 
                    tempS2[topS2++] = cinStr[i]; 
                }else{                                  // 如果有
                                                        // 将比自己 优先级高 或 相同的 运算符 弹出到后缀表达式 
                    if(campareToChar(tempS2[topS2 - 1]) >= campareToChar(cinStr[i])){
                        while(topS2 >0 && campareToChar(tempS2[topS2 - 1]) >= campareToChar(cinStr[i])){
                            stackS1[topS1++] = tempS2[--topS2]; 
                        }
                    } 
                    tempS2[topS2++] = cinStr[i];        // 将字符压如栈 
                } 
            } 
            i++;
        } 
        while(topS2-- > 0){
       // 最后 将栈里面的 剩余的 运算符 弹出 到 后缀表达式 
            stackS1[topS1++] = tempS2[topS2];
        }
    
        double temp = createToNum(stackS1, topS1); // 计算 
    
        cout << "stackS1(后缀表达式) = " << stackS1 << endl; // 打印结果 
        cout << "tempS2(临时栈) = " << tempS2 << endl;
        cout << "cinStr(输入的中缀表达式) = " << cinStr << endl; 
        cout << "计算出来的值为 = " << temp << endl; 
        system("pause");
        return 0;
    }
    double createToNum(char stack[], int len){
       // 将 转换的后缀表达式 计算出来 
        double num[1000] = {
       0};
        int numTop = 0;
        int i = 0; 
        while(i <= len){
    
            if(stack[i] <= '9' && stack[i] >= '0'){
                double x = 0;   // 记录 数字 
                int k  = 0;     // 记录小数位数 
                while(stack[i] <= '9' && stack[i] >= '0') {
       // 处理整数部分 
                    x = x * 10 + stack[i++] - '0'; 
                }
                if(stack[i] == '.'){
       // 处理小数部分 
                    i++; // 跳过小数点 
                    while(stack[i] <= '9' && stack[i] >= '0') {
       // 处理整数部分 
                        x = x * 10 + stack[i++] - '0'; 
                        k++;// 小数位数增加 
                    }
                    while(k-- > 0){
       // 转换成小数 
                        x = x / 10; 
                    }
                } 
                num[numTop++] = x;// 记录数字 
                i--; // 这里做了一下i-- 的处理 // 要不然会跳过 最后几个运算符 
                // 这里不懂可以 试着把 i-- 去掉运行 就知道了 
    
            } else{
       // 运算符 + - * / 
                switch(stack[i]){
                    case '+':num[numTop - 2] = num[numTop - 2] + num[numTop - 1]; 
                        numTop--; // 因为两个数运算生成一个 所以 数字减少一个 
                        break; 
                    case '-':num[numTop - 2] = num[numTop - 2] - num[numTop - 1];
                        numTop--; 
                        break; 
                    case '*':num[numTop - 2] = num[numTop - 2] * num[numTop - 1];
                        numTop--; 
                        break; 
                    case '/':num[numTop - 2] = num[numTop - 2] / num[numTop - 1];
                        numTop--; 
                        break; 
                    default: // 防止空格干扰 
                        break;
                }
            }
    // for(int j = 0; j < 4; j++){ 
    // cout << num[j] << "\t"; // 用来观察 过程
    // } 
    // cout << endl;
            i++;// 继续下一个 
        }
    // for(int j = 0; j < 4; j++){// 用来观察 过程
    // cout << num[j] << "\t"; 
    // } 
    // cout << endl; 
    
        return num[0]; // 计算好的结果 存在第一个 
    }

[70]: /images/20220528/0b5f00998af449728a5ae73607da996a.png