天天看点
返回

C++的STL 栈 实现四则运算

使用栈实现四则运算，支持+，-，*，/，(，)

输入为字符串，输出为计算好的数值，如不符合四则运算的规定，则异常退出

这个实现借用了栈以及字符处理状态机的思想：

  1. 维护两个栈：一个用于数值，另一个用于存放计算符号
  2. 字符状态机用于遍历输入的字符串过程中进行对应数值处理和计算符号处理的状态转换

在第一个思想中：符号栈中存在优先级，即*和/的优先级高于+和-，同时括号的优先级高于*和/，所以符号栈的入栈顺序以及触发计算时机需要在状态机转动的过程中谨慎处理。

入栈基本过程类似如下：

对于1+121的入栈过程如下

C++的STL 栈 实现四则运算

状态机的处理过程如下：

C++的STL 栈 实现四则运算

核心创建两个栈的算法如下(文末有完整测试代码)：

int state_change(string s) {
    static const int BEGIN_STATE = 0;
    static const int NUM_STATE = 1;
    static const int OPE_STATE = 2;
    int STATE = BEGIN_STATE;
    map<char,int> prio;
    stack<int> num_stack;
    stack<char> oper_stack;
    
    int cacl_flag = -1;
    int number = 0;
    
    /*设置运算符优先级*/
    prio['+'] = 1;
    prio['-'] = 1;
    prio['*'] = 2;
    prio['/'] = 2;
    prio['('] = 3;

    int i;
    if (s.empty()) {
        print_erro("string is empty\n",__LINE__);
    }

    for(int i = 0;i < s.size(); ++i) {
        if (s[i] == ' ') {
            continue;
        }
        switch (STATE)
        {
        case BEGIN_STATE: //初始状态
            if (s[i] >= '0' && s[i] <= '9') {
                STATE = NUM_STATE;
            } else if(s[i] == ')'){
                print_erro("string is not leagal\n",__LINE__);
            } else {
                STATE = OPE_STATE;
            }
            i--; //处理退格
            break;
            
        case NUM_STATE: //数字状态
            if (s[i] >= '0' && s[i] <= '9') {
                number = number*10 + s[i] - '0'; //将数值型字符串转换为数字
            } else {
                num_stack.push(number);
                if (cacl_flag == 2) { //优先计算*和/，+和-末尾计算
                    calculate(num_stack,oper_stack);
                }
                STATE = OPE_STATE;
                number = 0;
                i--;
            }
            break;

        case OPE_STATE: //字符状态
            if(prio[s[i]] == 1) { //+，- 字符入栈，设置计算优先级
                oper_stack.push(s[i]);
                cacl_flag = 1;
            } else if(prio[s[i]] == 2) {//*，/ 字符入账，设置计算优先级
                oper_stack.push(s[i]);
                cacl_flag = 2;
            } else if (prio[s[i]] == 3) { // 如果为左括号，则切换状态到数字
                cacl_flag = 3;
                STATE = NUM_STATE;
                break;
            } else if (s[i] == ')') { //如果为右括号，则进行计算
                calculate(num_stack,oper_stack);
                break;
            } else if(s[i] >= '0' && s[i] <= '9') {
                STATE = NUM_STATE;
                i--; //如果为数字，则处理退格，并进行状态切换
            } else {
                print_erro("string is not leagal \n",__LINE__);
            }

            break;
            
        default:
            break;
        }
    }

    if (number != 0) { //处理最后的数字入栈
        num_stack.push(number);
        calculate(num_stack,oper_stack);
    }

    if (number == 0 && num_stack.empty()) { 
        return 0;
    }
    while(!oper_stack.empty() && num_stack.size() != 1) { //处理数字栈和字符栈中的剩余数据
        calculate(num_stack,oper_stack);
    }

    if (!oper_stack.empty()) { //如果字符栈中还有字符，则为异常四则运算
        print_erro("string is not leagal", __LINE__);
    }

    return num_stack.top();
}

依据字符栈和数字栈进行计算的过程如下:

这里需要注意两个运算的取值上的顺序问题（从栈中取出来的数值和输入是相反的），减法需要进行取反操作，除法需要进行数值顺序反转操作

void calculate(stack<int> &num_stak, stack<char> &oper_stack) {
    int num1;
    int num2;
    int result;

    num1 = num_stak.top();
    num_stak.pop();
    num2 = num_stak.top();
    num_stak.pop();

    if (oper_stack.top() == '+') {
        result = num1 + num2;
    } else if (oper_stack.top() == '-') {
        result = -(num1 - num2); //减法取反
    } else if (oper_stack.top() == '*') {
        result = num1 * num2;
    } else if (oper_stack.top() == '/') {
        if (num1 == 0) {
            print_erro("divide num is 0 \n", __LINE__);
        }
        result = num2 / num1; //数值反转进行计算
    } else {
        print_erro("operator failed\n", __LINE__);
    }
    oper_stack.pop();
    num_stak.push(result);
}

完整代码如下:

#include <iostream>
#include <algorithm>
#include <stack>
#include <map>


using namespace std;

void print_erro(string s,int line) {
    cout << s <<" " << line << endl;
    exit(-1);
}

void calculate(stack<int> &num_stak, stack<char> &oper_stack) {
    int num1;
    int num2;
    int result;

    num1 = num_stak.top();
    num_stak.pop();
    num2 = num_stak.top();
    num_stak.pop();

    if (oper_stack.top() == '+') {
        result = num1 + num2;
    } else if (oper_stack.top() == '-') {
        result = -(num1 - num2);
    } else if (oper_stack.top() == '*') {
        result = num1 * num2;
    } else if (oper_stack.top() == '/') {
        if (num1 == 0) {
            print_erro("divide num is 0 \n", __LINE__);
        }
        result = num2 / num1;
    } else {
        print_erro("operator failed\n", __LINE__);
    }
    oper_stack.pop();
    num_stak.push(result);
}

int state_change(string s) {
    static const int BEGIN_STATE = 0;
    static const int NUM_STATE = 1;
    static const int OPE_STATE = 2;
    int STATE = BEGIN_STATE;
    map<char,int> prio;
    stack<int> num_stack;
    stack<char> oper_stack;
    
    int cacl_flag = -1;
    int number = 0;
    prio['+'] = 1;
    prio['-'] = 1;
    prio['*'] = 2;
    prio['/'] = 2;
    prio['('] = 3;

    int i;
    if (s.empty()) {
        print_erro("string is empty\n",__LINE__);
    }

    for(int i = 0;i < s.size(); ++i) {
        if (s[i] == ' ') {
            continue;
        }
        switch (STATE)
        {
        case BEGIN_STATE:
            if (s[i] >= '0' && s[i] <= '9') {
                STATE = NUM_STATE;
            } else if(s[i] == ')'){
                print_erro("string is not leagal\n",__LINE__);
            } else {
                STATE = OPE_STATE;
            }
            i--;
            break;
            
        case NUM_STATE:
            if (s[i] >= '0' && s[i] <= '9') {
                number = number*10 + s[i] - '0';
            } else {
                num_stack.push(number);
                if (cacl_flag == 2) {
                    calculate(num_stack,oper_stack);
                }
                STATE = OPE_STATE;
                number = 0;
                i--;
            }
            break;

        case OPE_STATE:
            if(prio[s[i]] == 1) {
                oper_stack.push(s[i]);
                cacl_flag = 1;
            } else if(prio[s[i]] == 2) {
                oper_stack.push(s[i]);
                cacl_flag = 2;
            } else if (prio[s[i]] == 3) {
                cacl_flag = 3;
                STATE = NUM_STATE;
                break;
            } else if (s[i] == ')') {
                calculate(num_stack,oper_stack);
                break;
            } else if(s[i] >= '0' && s[i] <= '9') {
                STATE = NUM_STATE;
                i--;
            } else {
                print_erro("string is not leagal \n",__LINE__);
            }

            break;
            
        default:
            break;
        }
    }

    if (number != 0) {
        num_stack.push(number);
        calculate(num_stack,oper_stack);
    }

    if (number == 0 && num_stack.empty()) {
        return 0;
    }
    while(!oper_stack.empty() && num_stack.size() != 1) {
        calculate(num_stack,oper_stack);
    }

    if (!oper_stack.empty()) {
        print_erro("string is not leagal", __LINE__);
    }

    return num_stack.top();
}

int main() {
    string s;
    cout << "input the string " << endl;
    cin >> s;
    int a = state_change(s);
    cout << "calcute the result is " << a << endl;
    return 0;
}      
(((1+5)/2+6*9+10)-(2+3)*100)
calcute the result is -433
入栈 优先级 #include
上一篇: Android 面试题笔记-------bindservice与startservice的生命周期？
下一篇: LSM 优化系列（二）-- dCompaction: Speeding up Compaction of the LSM-Tree via Delayed Compaction

继续阅读