Java教程

算法~简单的计算器(验证数学表达式是否合法~“状态机思想”)

本文主要是介绍算法~简单的计算器(验证数学表达式是否合法~“状态机思想”),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法~简单的计算器(验证数学表达式是否合法~“状态机思想”)

(有限状态机思想~进行状态转化,每个状态下,再进行判断是否转化状态)

1,为什么存储结构选择~栈?

因为栈可以去除括号,处理优先级~

举例:14-(5-6)

 2,计算思路:

(1)全局变量compute_flag 标志是否可以进行计算,初始comute_flag = 0; 遇到 “+”或者“-”时,compute_flag = 1;

遇到“(”,compute_flag = 0;

(2)字符串数处理为整型数:number = number * 10 + ch - ‘0’; 

【ps举例:String s="1234"; for(int i = 0; i < s.length(); i++){ number = number*10+s[i]-'0'; }】~‘ascall 码 相减(- ‘0’)获取该值 ’。

(3)状态机过程:循环遍历所有字符串元素:判断第一个字符串元素是否为空,空~continue;非空,进入startState~

stateState:若是(“0”~“9”)~进入numberState 状态;若是“(” 进入operationState状态。

然后,“退格”【因为循环体内部最后一行代码是 i++,退格回到s[i] 本身,进入numState 状态/opState状态。】

(全局变量:state、startState、numberState、opState)

(4) numberState 状态:

     如果遇到(“0”~“9”){//处理转化为整型数:number = number*10+s[i]-'0';   },否则 {

1,先将数number 压入数字栈number_stack;  [字符串元素 1 2 3  +  遇到 + ,才知道前三个元素构成一个数字]

2, 判断compute_state 是否为1,为1,则进行计算;

3,num=0;进入操作符状态operationState~【遇到 +】,退格 i--;}

(5) operationState状态:{

1,判断是“+” 或“-”,压入操作符栈operation_stack; 修改compute_flag = 1;

2,如果 遇到 "(", 修改compute_flag = 0; 进入数字状态 numberState~

3,如果遇到(“0”~“9”),进入数字状态 numberState,退格i --; ~

4,如果 遇到 ")", 直接进行计算

}

(6)最后一个数number的处理【为什么有最后一个数 ,因为 之前的字符串元素 1 2 3  +  遇到 + ,才知道前三个元素构成一个数字,将数压栈,

但是最后一个数是因为遍历结束,并非有 “+”的提示】:

如果number != 0,则 压入数字栈number_stack,然后进行计算;

如果number == 0 且 栈空了,结果就是 0;

 

3,代码:

❀ 计算方法:

/**
 * 计算
 */
void compute(std::stack<int> &number stack, std:: stack<char> &operation_stack){
    if(number_state.size() < 2){
        return;
    } 
    int num2 = number_state.top();
    number_state.pop();
    int num1 = number_state.top();
    number_state.pop();
    if(operation_stack.top() == '+'){
        number_state.push(num1 + num2);
    }else if(operation_stack.top() == '-'){
        number_state.push(num1 - num2);
    }
    operation_stack.pop();
}

❀ “状态机”过程的计算方法:

 

int calculate(std::String s){
    static const int START_STATE = 0;
    static const int NUMBER_STATE = 1;
    statci const int OPERATION_STATE = 2;
    std::stack<int> number_stack;
    std::stack<char> operation_stack;
    int number = 0;       //用于将字符串数处理为整型数
    int STATE = START_STATE;
    int compute_flag = 0;  //全局变量compute_flag 标志是否可以进行计算
    for(int i = 0; i < s.length(); i++){
        if(s[i] == '') continue;
        switch (STATE){
            case START_STATE:
                if(s[i] >= '0' && s[i] <= '9'){
                    STATE = NUMBER_STATE;
                }else {
                    STATE = OPERATION_STATE;
                }
                i--;    //退格,因为循环体内部最后一行代码是 i++,退格回到s[i] 本身
                break;
            case NUMBER_STATE:
                if(s[i] >= '0' && s[i] <= '9'){
                    number = number * 10 + s[i] - '0';
                }else{
                    number_stack(number);
                    if(compute_flag == 1){
                        compute(number_stack,operation_stack);
                    }
                    number = 0;
                    STATE = OPERATION_STATE;
                    i--;   //退格
                }
                break;
            case OPERATION_STATE:
                if(s[i] == '+' || s[i] == '-'){
                    operation_stack.push(s[i]);
                    compute_flag = 1;
                }else if(s[i] == '('){
                    STATE = NUMBER_STATE;
                    compute_flag = 0;
                }else if(s[i] >= '0' && s[i] <= '9'){
                    STATE = NUMBER_STATE;
                    i--;
                }else if(s[i] == ')'){
                    compute(number_stack,operation_stack);
                }
                break;
        }
    }
    
    //最后遍历凑成的一个数
    if(number != 0){
        number_stack.push(number);
        compute(number_stack,operation_stack);
    }else if(number == 0 && number_stack.empty()){
        return 0;
    }
    return number_stack.top();
}

 

 

 

 

 

 

 

 

 

这篇关于算法~简单的计算器(验证数学表达式是否合法~“状态机思想”)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!