c++用栈实现算术表达式的计算

用栈将算术表达式转换成后缀表达式的形式大家应该不陌生了,但是我在实现计算的时候却发现坑还是不少。

题目描述: 读入一个只包含 +, -, *, / 的非负整数计算表达式,计算该表达式的值。

输入描述: 测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输出。

输出描述: 对每个测试用例输出1行,即该表达式的值,精确到小数点后2位。

示例1 输入

1 + 2 4 + 2 * 5 - 7 / 11 0

输出

3.00 13.36

做这题必须注意几个问题:

  • 当栈里没有运算符的时候,直接对栈顶和字符串读取到的运算符进行比较会出错,因此这里在一开始就往栈里压入了一个我们设计的符号'#'
  • 当我们遍历字符串的时候,遇到数字要格外注意,因为此时一切都是字符形式了,比如说输入11就会变成两个字符1,因此我们在读取的时候要进行判断,确保所有连在一起的数字字符都读到了,而不是只读到了第一个字符。
  • 当我们遍历完字符串的时候,很有可能栈里还留有没处理的运算符,因此我们需要继续处理栈里的操作符,这里在字符串后面加入了符号\$是很巧妙的,\$的优先级比'#'高,比其他符号低,因此这保证了当读到字符\$时,它一定比栈顶出现的所有字符优先级高(除了它自己和'#'),这样就可以让栈里剩下的运算符一个一个弹出来,至到处理结束,栈顶为'#',压入\$。

具体代码如下:

#include<iostream>
#include<stack>
#include<string>
#include<stdio.h>
#include<cctype>
using namespace std;


/**
 * 比较操作符优先级的函数

 */
int OperPrecedence(char a){
    if(a == '/' || a == '*'){
        return 3;
    }else if(a == '+' || a == '-' ){
        return 2;
    }else if(a == '$'){
        return 1;
    }else if(a == '#'){
        return 0;
    }

}

/**
 * 实现运算
 */

double operNums(char oper, double num1, double num2){
    if(oper == '+'){
        return num1 + num2;
    }else if(oper == '-'){
        return num1 - num2;
    }else if(oper == '*'){
        return num1 * num2;
    }else if(oper == '/'){
        return num1 / num2;
    }
}

/**
 * 实现遇到数字往后移动直到数字确定
 */

int getNum(string str, int &index){
    string num = "";
    while(isdigit(str[index])){
        num += str[index];
        index ++;
    }

    return atoi(num.c_str());
}
int main(){
    stack<char> operStack;
    stack<double> numStack;
    string str;
    char oper;
    double num1;
    double num2;
    double sum = 0;
    int index = 0, preceResult;
    operStack.push('#');
    while (getline(cin, str))
    {

        str += '$';
        if(str[0] == '0'){
           
            break;
        }

        while(index < str.size()){
          
        if(str[index] == ' '){
            index++;
        }
        else if(isdigit(str[index])){
            //数字
            numStack.push(getNum(str, index));
        }else
        {
            //操作符
            //比较优先级

            if(OperPrecedence(operStack.top()) < OperPrecedence(str[index])){
                operStack.push(str[index]);
                index++;
            }else{
                num2 = numStack.top();
                numStack.pop();
                num1 = numStack.top();
                numStack.pop();
                oper = operStack.top();
                operStack.pop();
                numStack.push(operNums(oper, num1 ,num2));

            }
            
        }
        
        
        }
        // std::cout << "sum="<<sum << endl;
        printf("%.2f\n", numStack.top());
        index = 0;
        
        
    }
  


}


上一篇:Scala 前置、中置、后置操作符


下一篇:Spring学习笔记(2)——Bean的配置