注册 留言板
当前位置:首页 > 方法论 > 数据结构 > 正文

栈的应用:中缀和后缀表达式的转换及计算

来源:CNBLOGS   发布时间: 2017-06-19   作者:网友   浏览次数:
摘要: [TOC] 一、两种表达式 中缀表达式:人使用的类似于(2+3*5),运算符号在数字中间的表达式 后缀表达式:不包含括号,运算符放在...

[TOC]

一、两种表达式

中缀表达式:人使用的类似于(2+3*5),运算符号在数字中间的表达式

后缀表达式:不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则。这是计算机的计算方式。

二、转化规则和思路

利用栈,可以实现中缀表达式转化为后缀表达式。也可以实现后缀表达式的计算。这里主要实现难度较大的中缀表达式向后缀表达式的转化。

  1. 准备两个栈,一个符号栈:存放运算符号(用后销毁);另一个结果栈:存放后缀表达式。
  2. 将中缀表达式按顺序读入。
  3. 遇到数字就直接push进入结果栈。
  4. 遇到+-*/ 运算符,检查符号栈是否有运算级相同或更低的符号,一直pop后,再push进入结果栈。检查过程知道遇到更高级运算符停止。
  5. 遇到(左括号,直接入符号栈
  6. 遇到)右括号,将符号栈里面的符号pop,再push进入结果栈,直到遇到(停止。而两个括号都丢弃。
  7. 最后,将符号栈的剩余符号挨个弹出,再push进入结果栈。销毁不需要的符号栈。

三、代码实现

这个程序支持+-*/操作,支持字母和0-9的数字。网上的其他实现多是:遇到数字连续输出,再比较符号栈的内容再决定是否输出符号。这里新开了一个栈作为存储结果的结构。而最后的输出是倒序输出。

#include<iostream>
#include<string>
using namespace std;

template <class T>
class Stack{
    private:
        T *base;
        T *top;
        int size;
    public:
        Stack(int s);
        void Push(T);
        T Pop();
        int GetSize();
        void ClearStack();
        void DeleteStack();
};
template<class T>
Stack<T>::Stack(int s){
    size = s;
    base = new T [size];
    top = base;
}
template<class T>
void Stack<T>::Push(T elem){
    if(top - base >= size ){
        //下面自己实现relloc,重新申请空间 
        T *tem = new T [size];
        for(int i=0;i<size;++i)
            tem[i] = base[i];
        delete [] base;
        base = tem;
        top = base + size; //重新设置栈顶 (注意之前已经满了)
        size = size*2; //重新设置最大容量 
    }
    *top = elem;
    ++top;
}
template<class T>
T Stack<T>::Pop(){  
    if(top!=base){
        --top ; 
        T tem = *top;
        return tem;
    }
}
template<class T>
int Stack<T>::GetSize(){
    return top-base;
}
template<class T>
void Stack<T>::ClearStack(){
    top = base;
}
template<class T>
void Stack<T>::DeleteStack(){
    delete [] base;
    size = 0;
    base = top = NULL;
}

void GetResult(string eval,Stack<char> &result_stack){
    Stack <char>symbol_stack(10);//用来存放中缀表达式的符号栈 
    char tem;
    for (int i=0;i<eval.length();++i){ 
        if((eval[i]>='0' && eval[i]<='9') || (eval[i]>='a' && eval[i]<='z') || (eval[i]>='A' && eval[i]<='Z'))
            result_stack.Push(eval[i]);
        else if(eval[i]=='+' || eval[i]=='-'){
            if (!symbol_stack.GetSize())//如果空,直接推入 
                symbol_stack.Push(eval[i]);
            else{
                tem = symbol_stack.Pop();
                while(tem!='('){
                    result_stack.Push(tem);
                    if(symbol_stack.GetSize())
                        tem = symbol_stack.Pop();
                    else break;
                }
                if(tem=='(')
                    symbol_stack.Push(tem);
                symbol_stack.Push(eval[i]);
            }
        }
        else if(eval[i]==')'){ //右括号不需要推入,他只有匹配左括号的作用 
            tem = symbol_stack.Pop();
            while (tem!='('){
                result_stack.Push(tem);
                tem = symbol_stack.Pop();
            } //最终最括号也被弹出 
        }
        else if(eval[i]=='(')
            symbol_stack.Push(eval[i]);
        else if(eval[i]=='*' || eval[i]=='/'){
            if(!symbol_stack.GetSize())
                symbol_stack.Push(eval[i]);
            else{
                tem = symbol_stack.Pop();
                while(tem!='(' && tem!='+' && tem!='-'){
                    result_stack.Push(tem);
                    if(symbol_stack.GetSize())
                        tem = symbol_stack.Pop();
                    else
                        break;
                } 
                if(tem=='(' || tem=='+' || tem=='-')
                    symbol_stack.Push(tem);
                symbol_stack.Push(eval[i]);
            }
        }
        else ;
    }
    while(symbol_stack.GetSize())
        result_stack.Push(symbol_stack.Pop());
}
int main(){
    Stack <char>result_stack(10); //用来存放后缀表达式的符号和数据栈 
    string eval;
    cout<<"请输入表达式:(因为string实现,所以别有空格;且支持0-9和字母的+-*/和括号运算)"<<endl;
    cin>>eval; 
    GetResult(eval,result_stack);
    int i = 0,size = result_stack.GetSize();
    char *tem = new char [size];
    while(result_stack.GetSize()) 
        tem[i++]= result_stack.Pop();
    for(i=size-1;i>=0;--i){
        cout<<tem[i]<<" ";
    }
    cout<<endl;
    return 0;
}

四、计算后缀表达式的思路

后缀表达式的计算使用栈进行计算。如果遇到符号输入,那么就弹出前两个数据,进行运算,并且将结果再推入栈中。如果数据输入,那么直接入栈。这里输入假定是后缀表达式的格式。

代码较转换后缀表达式简单,因为没有那么多的判定条件,篇幅有限,这里不做实现了。


欢迎进一步交流本博文相关内容:

博客园地址 : http://www.cnblogs.com/AsuraDong/

CSDN地址 : http://blog.csdn.net/asuradong

也可以致信进行交流 : xiaochiyijiu@163.com

欢迎转载 , 但请指明出处  :  )




我来说两句
评论内容:
验  证  码:
 
(网友评论仅供其表达个人看法,并不表明本站同意其观点或证实其描述。)
评论列表
已有 0 条评论(查看更多评论)
精彩专题
友情链接:
设为首页 - 加入收藏 Copyright @2016 Infocool 版权所有 粤ICP备16000626号