注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

淡忘邻人

二十七,始发愤

 
 
 

日志

 
 
 
 

中缀表达式到后缀表达式 C#  

2010-06-02 09:49:39|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

中缀表达式是什么?

中缀表达式是一个通用的算术或逻辑公式表示方法,其表达式中操作符处于操作数的中间。例如表达式:(3+67)×5 , x&&(y|c)

中缀表达式不容易被电脑解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。

后缀表达式是什么?

不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:2 1 + 5 *,  即(2 + 1) * 5

后缀表达式优点是能够很容易被计算机所解析。 如上面的后缀表达式:2 1 + 5 *,  其中缀为 (2 + 1) * 5,

解析过程:

依次读取: 2 1 + 5 *

1.碰到数字就压入堆栈,如: 2,1 压入栈

2.碰到操作符就取出栈顶两个数操作,如:碰到了操作符‘+’  取出栈顶两个2 ,1  进行1+2=3

3.两个数操作结果再压压入堆栈 如:将3压入栈。

4.重复第1步,将5压入栈,

5.重复第2步,取出栈内 3,5 进行 3*5=15 (切记:top-2 操作符 top-1 = 结果)

最后结果:15

代码实现:

代码调用了一个堆栈,堆栈代码在:http://listsetio090529.blog.163.com/blog/static/13273218420105294750923/

public class InfixToSuffixExpression  
{  
    private Stack<char> _Stack = null;  
    private string _input;  
 
    public StringBuilder OutPutExpression { get; private set; }  
 
    public InfixToSuffixExpression(string inputExpression)  
    {  
        this._input = inputExpression;  
        _Stack = new Stack<char>(this._input.Length);  
        OutPutExpression = new StringBuilder();  
    }  
 
    public void Convert()  
    {  
        if (string.IsNullOrEmpty(this._input)) return;  
 
        foreach (char ch in this._input.ToCharArray())  
        {  
            if (Char.IsLetterOrDigit(ch))//it's letter or digit and push it directly.  
            { OutPutExpression.Append(ch); }  
            else 
            {  
                switch (ch)  
                {  
                    case '+':  
                    case '-':  
                        DoOperate(ch, 1);  
                        break;  
                    case '*':  
                    case '/':  
                        DoOperate(ch, 2);  
                        break;  
                    case '(':  
                        this._Stack.Push(ch);  
                        break;  
                    case ')':  
                        DoOperate();  
                        break;  
                    default:  
                        OutPutExpression.Append(ch);  
                        break;  
                }     
            }  
        }  
 
        DoOperate();  
    }  
 
    private void DoOperate(char ch, int level)  
    {  
        while (!this._Stack.IsEmpty)  
        {  
            char popChar = this._Stack.Pop();  
            if (popChar == '(')  
            {//it's left part list, nothing it.  
                this._Stack.Push(popChar); break;  
            }  
            else 
            {  
                int popCharlevel;  
                if (popChar == '+' || popChar == '-') { popCharlevel = 1; }  
                else { popCharlevel = 2; }//pop char is */  
 
                if (level > popCharlevel)  
                {//read*/ but the popchar is +-, then push it.  
                    this._Stack.Push(popChar); break;  
                }  
                else 
                { this.OutPutExpression.Append(popChar); }  
            }  
        }  
        this._Stack.Push(ch);  
    }  
    private void DoOperate()  
    {  
        while (!this._Stack.IsEmpty && this._Stack.GetTop() != '(')  
        {  
            this.OutPutExpression.Append(this._Stack.Pop());  
        }  
        this._Stack.Pop();//pop '('  
    }  


本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/fan158/archive/2010/04/07/5458918.aspx

  评论这张
 
阅读(586)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017