C++利用栈实现计算器

你的名字 2022-04-03 14:44 144阅读 0赞

**后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行，所以不需要算符优先级，这对我们编写计算器来说很好实现**

比如给定一个中缀表达式：

1 + 3 * 5 – ( 7 / 9 )

其后缀表达式应为：

1 3 5 * + 7 9 / -

**首先要理解如何进行转换,先按照运算优先级对其加上括号**

1 + 3 * 5 – ( 7 / 9 ) = ( (1 + (3 * 5 ) ) – ( 7 / 9 ) )

然后依次把优先级高的括号转为后缀

((1+(3*5)) – (7/9))
    --> ((1 + (35*)) – (79/))
    --> ((1 (35*)+) – 79/)   
    --> (135*+)(79/)-  
    --> 135*+79/-

## 整体步骤 ##

*  中缀表达式转后缀表达式
 *  计算后缀表达式

## 第一步： ##

**中缀表达式转后缀表达式**

自左向右读入中缀表达式

1.  数字时，加入后缀表达式；
2.  运算符：  
    \-若为 ‘(’，入栈  
    \-若为 ‘)’，则依次把栈中的的运算符加入后缀表达式中，直到出现’(’，从栈中删除’(’  
    \-若为除括号外的其他运算符， 当其优先级高于除’('以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止，然后将其自身压入栈中（先出后入）。
3.  当扫描的中缀表达式结束时，栈中的的所有运算符出栈；

## 具体图示：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70] ##

## 第二步 ##

**计算后缀表达式**  
建立一个栈S 。从左到右读表达式，如果读到操作数就将它压入栈S中，如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作数运算，再将运算的结果代替原栈顶的n项，压入栈S中 。如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。  
简言之：

1.  从左到右读表达式
2.  遇到操作数压入栈中
3.  遇到操作符取并弹出栈顶n个元素，（n取决于操作符是n元操作符），计算结果压入栈中
4.  后缀表达式读完，当前栈顶元素及为结果

## 代码如下 ##

#include <iostream>
    #include<stack>
    
    #include <sstream>
    #include<stdlib.h>
    using namespace std;
    
    double CalSuffix(string suffix)
    {
        double result;
        stack<double> number;
        int i = 0,j;
        int n=0;//判断是否为数字
        string current;
        while(suffix[i]!='#')
        {
            isNum=0;
            if(suffix[i]=='|')
            {
                for(j=i+1;; j++)
                {
                    if(suffix[j]=='|')
                        break;
                    if(suffix[j]=='#')
                        break;
                }
    
                //获取|A|之间元素
                for(int k=i+1; k<j; k++)
                {
                    current+=suffix[k];
                }
    
                //判断是否为数值
                for(int k=0; k<current.size(); k++)
                {
                    if(current[k]>=48 && current[k]<=57)//数字
                    {
                        //strinf转double
                        istringstream iss(current);
                        double num;
                        iss >> num;
                        number.push(num);
                        isNum = 1;
                        break;
                    }
                }
                if(isNum!=1){
                    double n2 = number.top();
                    number.pop();
                    double n1 = number.top();
                    number.pop();
                    if(current=="+"){
                        number.push(n1+n2);
                    }
                    else if(current=="-"){
                        number.push(n1-n2);
                    }
                    else if(current=="*"){
                        number.push(n1*n2);
                    }
                    else if(current=="/"){
                        number.push(n1/n2);
                    }
                }
                current="";//清空当前字符串;
            }
    
            i++;
        }
        if(number.size()!=1)
            cout<<"输入有误"<<endl;
        else
            return number.top();
    
    }
    
    
    int Priority(char operate)//栈中优先级
    {
        switch(operate)
        {
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 3;
        case '(':
        case ')':
            return 1;
        default:
            return 0;
        }
    }
    
    string Infix2Suffix(string Infix)
    {
        stack<char> operate;
        string Suffix = "                               ";//初始化后缀表达式
        char currentOp;
        int negative;
        int i = 0,j = 0;//i为中缀当前指向 j为后缀当前指向
        while(Infix[i]!='\0')
        {
            if(i+1!='\0')
                negative = 0;
            if(Infix[i]>=48 && Infix[i]<=57) //判断数字
            {
                Suffix[j++] = '|';//j是后缀表达索引
                Suffix[j++] =Infix[i];//存储当前数字并指向下一个
                while(Infix[++i]>=48 && Infix[i]<=57) //整数部分
                {
                    Suffix[j++] =Infix[i];
                }
                if(Infix[i]=='.') //是小数
                {
                    Suffix[j++]='.';
                    i+=1;//中缀索引 往后移
                    while(Infix[i]>=48 && Infix[i]<=57) //小数部分
                    {
                        Suffix[j++] =Infix[i];
                        i+=1;
                    }
                }
            }
            else if(Infix[i]=='(')//如果读入(，因为左括号优先级最高，因此放入栈中，但是注意，当左括号放入栈中后，则优先级最低。
            {
                operate.push(Infix[i++]);
            }
            else if(Infix[i]==')')//如果读入），则将栈中运算符取出放入输出字符串，直到取出（为止，注意：（）不输出到输出字符串。
            {
    
                if(operate.empty())//没有左括号
                    cout<<"表达式错误"<<endl;
                else
                {
                    currentOp = operate.top();
                    while(currentOp!='(')
                    {
                        cout<<currentOp<<endl;
                        Suffix[j++]='|';
                        Suffix[j++]=currentOp;
                        operate.pop();
                        if(operate.empty())
                        {
                            cout<<"表达式错误"<<endl;
                            break;
                        }
                        currentOp = operate.top();
                    }
                    operate.pop();//删除栈中(
                    i++;
                }
            }
    
            else if(Infix[i]=='+'||Infix[i]=='-'||Infix[i]=='/'||Infix[i]=='*')
            {
                //判断负数
                if(Infix[i]=='-')
                {
    
                    if(i==0)//第一个为‘-’时为负号
                        negative = 1;
                    else if(Infix[i-1]=='+'||Infix[i-1]=='-'||Infix[i-1]=='/'||Infix[i-1]=='*')//如果前面有操作符则为负号
                        negative = 1;
                    if(negative==1)
                    {
                        Suffix[j++] = '|';//负号
                        Suffix[j++] = '-';
                        i+=1;
                        if(Infix[i]>=48 && Infix[i]<=57) //判断数字
                        {
                            Suffix[j++] =Infix[i];
                            while(Infix[++i]>=48 && Infix[i]<=57) //整数部分
                            {
                                Suffix[j++] =Infix[i];
                            }
                            if(Infix[i]=='.') //是小数
                            {
                                Suffix[j++]='.';
                                i+=1;
                                while(Infix[i]>=48 && Infix[i]<=57) //小数部分
                                {
                                    Suffix[j++] =Infix[i];
                                    i+=1;
                                }
                            }
                        }
                        continue;
                    }
                }
    
                //如果读入一般运算符如+-*/，则放入堆栈，但是放入堆栈之前必须要检查栈顶
                if(operate.empty())
                {
                    operate.push(Infix[i++]);
                }
                else
                {
                    char top = operate.top();//栈顶
                    if(Priority(top)<Priority(Infix[i])) //放入的符号优先级低于栈顶
                    {
                        operate.push(Infix[i++]);//放入栈顶并指向下一个
                    }
                    else//如果放入的优先级较低，则需要将栈顶的运算符放入输出字符串。
                    {
                        while(Priority(top)>=Priority(Infix[i]))
                        {
                            Suffix[j++]='|';
                            Suffix[j++]=top;
                            operate.pop();
                            if(!operate.empty())
                            {
                                top = operate.top();
                            }
                            else
                                break;
                        }
                        operate.push(Infix[i++]);//放入栈顶并指向下一个
                    }
                }
    
            }
            else
            {
                cout<<"符号错误"<<endl;
                i+=1;
            }
        }
    
        //顺序读完表达式，如果栈中还有操作符，则弹出，并放入输出字符串。
        while(!operate.empty())
        {
            char to = operate.top();
            Suffix[j++]='|';
            Suffix[j++]=to;
            operate.pop();
        }
        Suffix[j] = '#';//结束符
        cout<<Suffix<<endl;
        return Suffix;
    }
    
    int main()
    {
        string a;
        cin>>a;
        istringstream iss(a);
        double num;
        iss >> num;
        cout<<num;
        cout<<"后缀为："<<Infix2Suffix(a)<<endl;
        cout<<CalSuffix(Infix2Suffix(a));
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70]: /images/20220403/dad3ad89404d46de905ac95d5b046fec.png