必威-必威-欢迎您

必威,必威官网企业自成立以来,以策略先行,经营致胜,管理为本的商,业推广理念,一步一个脚印发展成为同类企业中经营范围最广,在行业内颇具影响力的企业。

学习到栈的作用就好必威:,看看手机中的计算

2019-09-27 22:08 来源:未知

用C语言实现的带括号四则运算计算器,原理简单,即模拟笔算,将每个运算符标记等级,计算时按照等级由高到低进行计算。加减运算为0级,乘除运算为1级,每进入一层括号等级加2。使用两个链表分别储存运算符与数字。主程序调用之前实现的两个模块,一个是链表,另一个是分数计算。链表代码在下一篇文章,只贴出主程序和分数计算部分。

修改BUG的时候一不小心BUG越修越多,鉴于维护程序并不是学习数据结构的初衷,我已经果断的弃坑了!!

看看手机中的计算器,分为普通计算器和科学计算器

简易的JS计算器实现代码,js计算器代码

看看手机中的计算器,分为普通计算器和科学计算器

必威 1

 自认脑袋不够大,就实现一个普通版本的吧(支持正负数加减乘除等基本连续的运算,未提供括号功能)

看看图示效果:

必威 2

一、知识准备

1+1 = ?

正常来说,我们看到这个表达式都知道怎么运算,知道运算结果

但计算机不一样,计算机无法识别出这串表达式,它只能识别特定的规则:前缀表达式+ 1 1 或后缀表达式1 1 +

举个栗子

(3 + 4) × 5 - 6 就是中缀表达式

  • × + 3 4 5 6 前缀表达式
    3 4 + 5 × 6 - 后缀表达式 

所以为了实现程序的自动运算,我们需要将输入的数据转化为前缀或后缀表达式

前缀、中缀、后缀表达式的概念以及相互转换方法在这里就不多说了,这篇博文 说得比较清楚了

所以,在这个计算器的实现中,采用了后缀表达式的实现方式,参考以上文章,重点关注这两个算法:

与转换为前缀表达式相似,遵循以下步骤:
(1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
(2) 从左至右扫描中缀表达式;
(3) 遇到操作数时,将其压入S2;
(4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
(4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
(4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
(4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
(5) 遇到括号时:
(5-1) 如果是左括号“(”,则直接压入S1;
(5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
(6) 重复步骤(2)至(5),直到表达式的最右边;
(7) 将S1中剩余的运算符依次弹出并压入S2;
(8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。

与前缀表达式类似,只是顺序是从左至右:
从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
例如后缀表达式“3 4 + 5 × 6 -”:
(1) 从左至右扫描,将3和4压入堆栈;
(2) 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素,注意与前缀表达式做比较),计算出3+4的值,得7,再将7入栈;
(3) 将5入栈;
(4) 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
(5) 将6入栈;
(6) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。

二、实现过程

第一步当然是搭建计算器的页面结构,不是科学计算器,只提供了基本的运算功能,但也能即时地进行运算,显示出完整的中缀表达式,运算后保存上一条运算记录。

要先说一下:本来想实现小数点功能的,但小数点的存在让数据存储与数据显示的实现有了压力,实现过程实在脑大,索性先取消这个功能。 

1. 页面结构:

  <h5>计算计算</h5>
  <!-- 计算器 -->
  <div class="calc-wrap">
    <div class="calc-in-out">
      <!-- 上一条运算记录 -->
      <p class="calc-history" title=""></p>
      <!-- 输入的数据 -->
      <p class="calc-in"></p>
      <!-- 输出的运算结果 -->
      <p class="calc-out active"></p>
    </div>
    <table class="calc-operation">
      <thead></thead>
      <tbody>
        <tr>
          <td data-ac="cls" class="cls">C</td>
          <td data-ac="del">←</td>
          <td data-ac="sq">x<sup>2</sup></td>
          <td data-ac="mul">×</td>
        </tr>
        <tr>
          <td data-val="7">7</td>
          <td data-val="8">8</td>
          <td data-val="9">9</td>
          <td data-ac="div">÷</td>
        </tr>
        <tr>
          <td data-val="4">4</td>
          <td data-val="5">5</td>
          <td data-val="6">6</td>
          <td data-ac="plus">+</td>
        </tr>
        <tr>
          <td data-val="1">1</td>
          <td data-val="2">2</td>
          <td data-val="3">3</td>
          <td data-ac="minus">-</td>
        </tr>
          <td data-ac="per">%</td>
          <td data-val="0">0</td>
          <td data-ac="dot">.</td>
          <td data-ac="eq" class="eq">=</td>
      </tbody>
    </table>
  </div>

2. 结合一点样式:

body {
  padding: 20px;
  font-family: Arial;
}

.calc-wrap {
  width: 300px;
  border: 1px solid #ddd;
  border-radius: 3px;
}


.calc-operation {
  width: 100%;
  border-collapse: collapse;
}

.calc-in-out {
  width: 100%;
  padding: 10px 20px;
  text-align: right;
  box-sizing: border-box;
  background-color: rgba(250, 250, 250, .9);
}
.calc-in-out p {
  overflow: hidden;
  margin: 5px;
  width: 100%;
}
.calc-history {
  margin-left: -20px;
  font-size: 18px;
  color: #bbb;
  border-bottom: 1px dotted #ddf;
  min-height: 23px;
}

.calc-in,
.calc-out {
  font-size: 20px;
  color: #888;
  line-height: 39px;
  min-height: 39px;
}

.calc-in {
  color: #888;
}
.calc-out {
  color: #ccc;
}

.calc-in.active,
.calc-out.active {
  font-size: 34px;
  color: #666;
}

.calc-operation td {
  padding: 10px;
  width: 25%;
  text-align: center;
  border: 1px solid #ddd;
  font-size: 26px;
  color: #888;
  cursor: pointer;
}

.calc-operation td:active {
  background-color: #ddd;
}

.calc-operation .cls {
  color: #ee8956;
}

这样静态的计算器就粗来了~~

 必威 3

3. JS逻辑

这部分就是重点了,一步步来说

首先是对计算器的监听吧,也就是这个表格,可以使用事件委托的方式,在父级节点上监听处理

    // 绑定事件
    bindEvent: function() {
      var that = this;

      that.$operation.on('click', function(e) {
        e = e || window.event;
        var elem = e.target || e.srcElement,
          val,
          action;

        if (elem.tagName === 'TD') {
          val = elem.getAttribute('data-val') || elem.getAttribute('data-ac');  

监听数据,获取到的只是页面上的某个值/操作符,所以需要将数据存储起来形成中缀,再由中缀转换成后缀,最后通过后缀进行计算

    // 中缀表达式
    this.infix = [];
    // 后缀表达式
    this.suffix = [];
    // 后缀表达式运算结果集
    this.result = [];

按照算法步骤,实现出来,这里没有使用到括号,如果实际需要,可在相应位置修改判断条件即可~

    // 中缀表达式转后缀
    infix2Suffix: function() {
      var temp = [];
      this.suffix = [];

      for (var i = 0; i < this.infix.length; i++) {
        // 数值,直接压入
        if (!this.isOp(this.infix[i])) {
          this.suffix.push(this.infix[i]);
        }
        else {
          if (!temp.length) {
            temp.push(this.infix[i]);
          }
          else {
            var opTop = temp[temp.length - 1];
            // 循环判断运算符优先级,将运算符较高的压入后缀表达式
            if (!this.priorHigher(opTop, this.infix[i])) {
              while (temp.length && !this.priorHigher(opTop, this.infix[i])) {
                this.suffix.push(temp.pop());
                opTop = temp[temp.length - 1];
              }
            }
              // 将当前运算符也压入后缀表达式
            temp.push(this.infix[i]);
          }
        }
      }
      // 将剩余运算符号压入
      while (temp.length) {
        this.suffix.push(temp.pop());
      }
    },

 // 后缀表达式计算
    calcSuffix: function() {
      this.result = [];

      for (var i = 0; i < this.suffix.length; i++) {
        // 数值,直接压入结果集
        if (!this.isOp(this.suffix[i])) {
          this.result.push(this.suffix[i]);
        }
        // 运算符,从结果集中取出两项进行运算,并将运算结果置入结果集合
        else {
          this.result.push(this.opCalc(this.result.pop(), this.suffix[i], this.result.pop()));
        }
      }
      // 此时结果集中只有一个值,即为结果
       return this.result[0];
    }

其实,在实现的时候会发现,中缀、后缀只是一个难点,更复杂的地方是整个计算器的状态变化(或者说是数据变化)

在这个简单的计算器中,就有数字(0-9)、运算符(+ - * /)、操作(清除 删除)、预运算(百分号 平方)、小数点、即时运算等数据及操作

如果是科学计算器那就更复杂了,所以理清如何控制这些东西很关键,而其中最重要的就是中缀表达式的构建与存储

 当连续点击+号时,是不符合实际操作的,所以需要一个变量 lastVal 来记录上一个值,随着操作而更新,再通过判断,防止程序出错

在点击=号之后,我们可以继续使用这个结果进行运算,或者重新开始运算

    // 构建中缀表达式
    buildInfix: function(val, type) {
      // 直接的点击等于运算之后,
      if (this.calcDone) {
        this.calcDone = false;
        // 再点击数字,则进行新的运算
        if (!this.isOp(val)) {
          this.resetData();
        }
        // 再点击运算符,则使用当前的结果值继续进行运算
        else {
          var re = this.result[0];
          this.resetData();
          this.infix.push(re);
        }

      }

      var newVal;
       ...

点击删除,是删除一位数,不是直接地删除一个数,然后更新中缀表达式的值

      // 删除操作
      if (type === 'del') {
        newVal = this.infix.pop();
        // 删除末尾一位数
        newVal = Math.floor(newVal / 10);
        if (newVal) {
          this.infix.push(newVal);
        }

        this.lastVal = this.infix[this.infix.length - 1];
        return this.infix;
      }  

而添加操作,要考虑的就更多了,比如连续的连续运算符、连续的数字、运算符+

  • 接上数字表示正负数,小数点的连接存取等

        // 添加操作,首先得判断运算符是否重复
        else if (type === 'add') {
          // 两个连续的运算符
          if (this.isOp(val) && this.isOp(this.lastVal)) {
            return this.infix;
          }
          // 两个连续的数字
          else if (!this.isOp(val) && !this.isOp(this.lastVal)) {
            newVal = this.lastVal * 10 + val;
            this.infix.pop();
            this.infix.push(this.lastVal = newVal);
    
            return this.infix;
          }
          // 首个数字正负数
          if (!this.isOp(val) && this.infix.length === 1 && (this.lastVal === '+' || this.lastVal === '-')) {
            newVal = this.lastVal === '+' ? val : 0 - val;
            this.infix.pop();
            this.infix.push(this.lastVal = newVal);
    
            return this.infix;
          }
    
        this.infix.push(this.lastVal = val);
        return this.infix;
      }

在很多次操作的时候,计算器都需要即时地进行运算,为简化代码,可以封装成一个方法,在相应的位置调用即可

    // 即时得进行运算
    calculate: function(type) {
      this.infix2Suffix();
      var suffixRe = this.calcSuffix();

      if (suffixRe) {
        this.$out.text('=' + suffixRe)
          .attr('title', suffixRe)
          .removeClass('active');

        // 如果是直接显示地进行等于运算
        if (type === 'eq') {
          this.$in.removeClass('active');
          this.$out.addClass('active');
          // 设置标记:当前已经显示地进行计算
          this.calcDone = true;
          this.lastVal = suffixRe;
          // 设置历史记录
          var history = this.infix.join('') + ' = ' + suffixRe;
          this.$history.text(history).attr('title', history);
        }

      }
    },

剩下的就是点击之后的处理过程了,也就是各种调用处理 传递数据->构建中缀处理数据->中缀转后缀->后缀运算显示

比如点击了数字

          // 数字:0-9
          if (!isNaN(parseInt(val, 10))) {
            // 构建中缀表达式并显示
            var infixRe = that.buildInfix(parseInt(val, 10), 'add');
            that.$in.text(infixRe.join('')).addClass('active');

            that.calculate();

            return;
          }

又比如几个预运算,其实长得也差不多

       // 预运算:百分比、小数点、平方
          else if (['per', 'dot', 'sq'].indexOf(action) !== -1) {
            if (!that.infix.length || that.isOp(that.lastVal)) {
              return;
            }

            if (action === 'per') {
              that.lastVal /= 100;
            } else if (action === 'sq') {
              that.lastVal *= that.lastVal;
            } else if (action === 'dot') {
              // that.curDot = true;
            }

            // 重新构建中缀表达式
            var infixRe = that.buildInfix(that.lastVal, 'change');
            that.$in.text(infixRe.join('')).addClass('active');

            that.calculate();
          }

以上就是这个简单计算器的实现步骤了,变化太多还不敢保证不会出错

基本逻辑如此,如果要加上小数点运算、括号运算、正余弦等科学计算器的功能,还是自己去实现吧。。脑大啊。。 

$(function() {

  function Calculator($dom) {
    this.$dom = $($dom);
    // 历史运算
    this.$history = this.$dom.find('.calc-history');
    // 输入区
    this.$in = this.$dom.find('.calc-in');
    // 输出区
    this.$out = this.$dom.find('.calc-out');
    this.$operation = this.$dom.find('.calc-operation');

    // 运算符映射
    this.op = {
      'plus': '+',
      'minus': '-',
      'mul': '*',
      'div': '/'
    };
    this.opArr = ['+', '-', '*', '/'];

    // 中缀表达式
    this.infix = [];
    // 后缀表达式
    this.suffix = [];
    // 后缀表达式运算结果集
    this.result = [];
    // 存储最近的值
    this.lastVal = 0;
    // 当前已经计算等于完成
    this.calcDone = false;
    // 当前正在进行小数点点(.)相关值的修正
    this.curDot = false;

    this.init();
  }

  Calculator.prototype = {
    constructor: Calculator,
    // 初始化
    init: function() {
      this.bindEvent();
    },
    // 绑定事件
    bindEvent: function() {
      var that = this;

      that.$operation.on('click', function(e) {
        e = e || window.event;
        var elem = e.target || e.srcElement,
          val,
          action;

        if (elem.tagName === 'TD') {
          val = elem.getAttribute('data-val') || elem.getAttribute('data-ac');
          // 数字:0-9
          if (!isNaN(parseInt(val, 10))) {
            // 构建中缀表达式并显示
            var infixRe = that.buildInfix(parseInt(val, 10), 'add');
            that.$in.text(infixRe.join('')).addClass('active');

            that.calculate();

            return;
          }

          action = val;

          // 操作:清除、删除、计算等于
          if (['cls', 'del', 'eq'].indexOf(action) !== -1) {
            if (!that.infix.length) {
              return;
            }

            // 清空数据
            if (action === 'cls' || (action === 'del' && that.calcDone)) {
              that.$in.text('');
              that.$out.text('');

              that.resetData();
            }
            // 清除
            else if (action === 'del') {
              // 重新构建中缀表达式
              var infixRe = that.buildInfix(that.op[action], 'del');
              that.$in.text(infixRe.join('')).addClass('active');

              that.calculate();

            }
            // 等于
            else if (action === 'eq') {
              that.calculate('eq');

            }
          }
          // 预运算:百分比、小数点、平方
          else if (['per', 'dot', 'sq'].indexOf(action) !== -1) {
            if (!that.infix.length || that.isOp(that.lastVal)) {
              return;
            }

            if (action === 'per') {
              that.lastVal /= 100;
            } else if (action === 'sq') {
              that.lastVal *= that.lastVal;
            } else if (action === 'dot') {
              // that.curDot = true;
            }

            // 重新构建中缀表达式
            var infixRe = that.buildInfix(that.lastVal, 'change');
            that.$in.text(infixRe.join('')).addClass('active');

            that.calculate();
          }
          // 运算符:+ - * /
          else if (that.isOp(that.op[action])) {
            if (!that.infix.length && (that.op[action] === '*' || that.op[action] === '/')) {
              return;
            }

            var infixRe = that.buildInfix(that.op[action], 'add');
            that.$in.text(infixRe.join('')).addClass('active');
          }
        }
      });
    },

    resetData: function() {
      this.infix = [];
      this.suffix = [];
      this.result = [];
      this.lastVal = 0;
      this.curDot = false;
    },

    // 构建中缀表达式
    buildInfix: function(val, type) {
      // 直接的点击等于运算之后,
      if (this.calcDone) {
        this.calcDone = false;
        // 再点击数字,则进行新的运算
        if (!this.isOp(val)) {
          this.resetData();
        }
        // 再点击运算符,则使用当前的结果值继续进行运算
        else {
          var re = this.result[0];
          this.resetData();
          this.infix.push(re);
        }

      }

      var newVal;

      // 删除操作
      if (type === 'del') {
        newVal = this.infix.pop();
        // 删除末尾一位数
        newVal = Math.floor(newVal / 10);
        if (newVal) {
          this.infix.push(newVal);
        }

        this.lastVal = this.infix[this.infix.length - 1];
        return this.infix;
      }
      // 添加操作,首先得判断运算符是否重复
      else if (type === 'add') {
        // 两个连续的运算符
        if (this.isOp(val) && this.isOp(this.lastVal)) {
          return this.infix;
        }
        // 两个连续的数字
        else if (!this.isOp(val) && !this.isOp(this.lastVal)) {
          newVal = this.lastVal * 10 + val;
          this.infix.pop();
          this.infix.push(this.lastVal = newVal);

          return this.infix;
        }
        // 首个数字正负数
        if (!this.isOp(val) && this.infix.length === 1 && (this.lastVal === '+' || this.lastVal === '-')) {
          newVal = this.lastVal === '+' ? val : 0 - val;
          this.infix.pop();
          this.infix.push(this.lastVal = newVal);

          return this.infix;
        }

      // TODO: 小数点运算
      //   if (this.isOp(val)) {
      //     this.curDot = false;
      //   }

      //   // 小数点
      //   if (this.curDot) {
      //     var dotLen = 0;
      //     newVal = this.infix.pop();
      //     dotLen = newVal.toString().split('.');
      //     dotLen = dotLen[1] ? dotLen[1].length : 0;

      //     newVal += val / Math.pow(10, dotLen + 1);
      //     // 修正小数点运算精确值
      //     newVal = parseFloat(newVal.toFixed(dotLen + 1));

      //     this.infix.push(this.lastVal = newVal);
      //     return this.infix;
      //   }

        this.infix.push(this.lastVal = val);
        return this.infix;
      }

      // 更改操作,比如%的预运算
      else if (type === 'change') {
        this.infix.pop();
        this.infix.push(this.lastVal = val);

        return this.infix;
      }

    },
    // 判断是否为运算符
    isOp: function(op) {
      return op && this.opArr.indexOf(op) !== -1;
    },
    // 判断运算符优先级
    priorHigher: function(a, b) {
      return (a === '+' || a === '-') && (b === '*' || b === '/');
    },
    // 进行运算符的运算
    opCalc: function(b, op, a) {
      return op === '+'
        ? a + b
        : op === '-'
        ? a - b
        : op === '*'
        ? a * b
        : op === '/'
        ? a / b
        : 0;
    },
    // 即时得进行运算
    calculate: function(type) {
      this.infix2Suffix();
      var suffixRe = this.calcSuffix();

      if (suffixRe) {
        this.$out.text('=' + suffixRe)
          .attr('title', suffixRe)
          .removeClass('active');

        // 如果是直接显示地进行等于运算
        if (type === 'eq') {
          this.$in.removeClass('active');
          this.$out.addClass('active');
          // 设置标记:当前已经显示地进行计算
          this.calcDone = true;
          this.lastVal = suffixRe;
          // 设置历史记录
          var history = this.infix.join('') + ' = ' + suffixRe;
          this.$history.text(history).attr('title', history);
        }

      }
    },

    // 中缀表达式转后缀
    infix2Suffix: function() {
      var temp = [];
      this.suffix = [];

      for (var i = 0; i < this.infix.length; i++) {
        // 数值,直接压入
        if (!this.isOp(this.infix[i])) {
          this.suffix.push(this.infix[i]);
        }
        else {
          if (!temp.length) {
            temp.push(this.infix[i]);
          }
          else {
            var opTop = temp[temp.length - 1];
            // 循环判断运算符优先级,将运算符较高的压入后缀表达式
            if (!this.priorHigher(opTop, this.infix[i])) {
              while (temp.length && !this.priorHigher(opTop, this.infix[i])) {
                this.suffix.push(temp.pop());
                opTop = temp[temp.length - 1];
              }
            }
              // 将当前运算符也压入后缀表达式
            temp.push(this.infix[i]);
          }
        }
      }
      // 将剩余运算符号压入
      while (temp.length) {
        this.suffix.push(temp.pop());
      }
    },

    // 后缀表达式计算
    calcSuffix: function() {
      this.result = [];

      for (var i = 0; i < this.suffix.length; i++) {
        // 数值,直接压入结果集
        if (!this.isOp(this.suffix[i])) {
          this.result.push(this.suffix[i]);
        }
        // 运算符,从结果集中取出两项进行运算,并将运算结果置入结果集合
        else {
          this.result.push(this.opCalc(this.result.pop(), this.suffix[i], this.result.pop()));
        }
      }
      // 此时结果集中只有一个值,即为结果
       return this.result[0];
    }
  };

  new Calculator('.calc-wrap');
});

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持帮客之家。

看看手机中的计算器,分为普通计算器和科学计算器 自认脑袋不够大,就实现一个普通版本的吧(...

主程序,检查算式是否合法的函数未实现

以下内容再不更新,Github上的代码直接无法正常编译运行。。。。

必威 4

必威 5必威 6

参考参考就好,学习到栈的作用就好。。。

 自认脑袋不够大,就实现一个普通版本的吧(支持正负数加减乘除等基本连续的运算,未提供括号功能)

  1 #include "list.h"  2 #include "sz.h"  3   4 /*内部类型、常量、函数*/  5   6 #define LEVEL_NUM 20    //支持的运算级数  7   8 typedef struct  9 { 10     List *oper;    //存运算符的链表,data段类型为Op * 11     List *num;    //存数字的链表,data段类型为Fract * 12     int oper_num[LEVEL_NUM];    //存每一级的运算符个数 13 }Pack; 14  15 typedef struct 16 { 17     char oper; 18     int level; 19 }Op;    //运算符及对应的级别,加减0级,乘除1级,每进入一层括号运算符对应的级别加2 20  21  22 static void Convert(char equation[],Pack *pack); 23 static int str2int(char str[],int start,int end); 24 static int GetSE(char str[],int s,int flag); 25 static void Compute(Pack *pack,Fract *ans); 26  27  28 int main(void) 29 { 30     char equation[100]; 31     Fract ans; 32     while(1) 33     { 34         scanf("%s",equation); 35         calc(equation,&ans); 36         printf("%d/%dn",ans.numer,ans.deno); 37     } 38     return 0; 39 } 40  41 void calc(char equation[],Fract *ans) 42 { 43     Pack pack; 44  45     //检查及完善equation,该函数未实现!! 46  47     //转换并存入链表 48     Convert(equation,&pack); 49  50     //使用链表计算,并释放 51     Compute(&pack,ans); 52  53 } 54  55 //特别说明 56 //对于"(-数字"这种形式,会导致str2int的参数start>end,正好会转化成"(0-数字"的形式 57 //因此没有用库函数 58 void Convert(char equation[],Pack *pack) 59 { 60     int i,base,start; 61  62     Op *op; 63     Fract *num; 64  65     //初始化 66     pack->num=CreateList(); 67     pack->oper=CreateList(); 68     for(i=0;i<LEVEL_NUM;i++) 69         pack->oper_num[i]=0; 70  71     start=GetSE(equation,0,1); 72     base=0;    //存级别的基,每进入一层括号基加2 73     for(i=0;equation[i];i++) 74         switch(equation[i]) 75         { 76         case '+':case '-':case '*':case '/': 77             //添加运算符 78             op=malloc(sizeof; 79             op->oper=equation[i]; 80             op->level=base+ 81                 ( (equation[i]=='+'||equation[i]=='-')?0:1); 82             AddNode(pack->oper,op,pack->oper->n);    //插入到链表尾 83             pack->oper_num[op->level]++; 84              85             //添加数字 86             num=malloc(sizeof; 87             num->numer=str2int(equation,start,GetSE(equation,i-1,-1)); 88             num->deno=1; 89             AddNode(pack->num,num,pack->num->n); 90             start=GetSE(equation,i+1,1);    //为下一个数字准备 91             break; 92         case '(': 93             base+=2; 94             break; 95         case ')': 96             base-=2; 97             break; 98         default:    //数字字符 99             break;100         }101 102     //运算符和数字成对出现,存入最后多出的数字103     num=malloc(sizeof;104     num->numer=str2int(equation,start,GetSE(equation,i-1,-1));105     num->deno=1;106     AddNode(pack->num,num,pack->num->n);107 }108 109 110 //将由start和end脚标确定的字符串转换为整数111 int str2int(char str[],int start,int end)112 {113     int i,s=0;114     for(i=start;i<=end;i++)115         s=s*10+str[i]-'0';116     return s;117 }118 119 120 //从s开始向前或向后找第一个数字字符的角标121 //flag为1向后,-1向前122 int GetSE(char str[],int s,int flag)123 {124     int i;125     for(i=s;i>=0 && str[i] && !isdigit;i+=flag)126         ;127     return i;128 }129 130 void Compute(Pack *pack,Fract *ans)131 {132     //前一运算符,运算符133     //第一个数字,第二个数字    134     Node *pop,*op,*num,*nnum;    135     int i;136 137     //找到最高不为0的一级138     for(i=LEVEL_NUM-1;i>=0 && !pack->oper_num[i];i--)139         ;140 141     for(;i>=0;i--)    //由高到低级依次计算142         for(pop=pack->oper->head,op=pack->oper->head->next,num=pack->num->head->next;143         pack->oper_num[i] ;    )144             if(op->data))->level==i )    //找到级别为i的运算符145             {146                 pack->oper_num[i]--;147                 switch(op->data))->oper)148                 {149                 //计算,结果存入第一个数中150                 case '+':Plus(num->data,num->next->data);151                     break;152                 case '-':Minus(num->data,num->next->data);153                     break;154                 case '*':Multiply(num->data,num->next->data);155                     break;156                 case '/':Divide(num->data,num->next->data);157                     break;158                 default:    159                     printf("nCompute函数出现不可能运算符 %cn",(op->data))->oper);160                     exit(0);161                     break;162                 }163 164                 //删除计算完成的运算符、数字165                 pack->num->n--;166                 pack->oper->n--;167                 pop->next=op->next;168                 nnum=num->next;169                 num->next=nnum->next;170                 free(nnum->data);free(op->data);171                 free;free;172 173                 op=pop->next;    //恢复op的指向174             }175             else    //没找到时继续遍历链表176                 pop=op,op=op->next,num=num->next;177 178     //计算完成后,仅剩一个的数字为结果,运算符链表没内容,储存运算符级别的个数的数组各元素为0179     if(pack->num->n!=1 || pack->oper->n || pack->oper_num[0])180     {181         printf("Compute函数内变量异常,数字个数 %d,运算符个数 %d,0级个数 %d",182                             pack->num->n,pack->oper->n,pack->oper_num[0]);183         exit(0);184     }185     =*pack->num->head->next->data;186     DestroyList(pack->num);187     DestroyList(pack->oper);188 }

===========================================================

看看图示效果:

sz.c必威 7必威 8

使用数据结构中的栈以及链表来制作一个能够处理中缀表达式的计算程序。

必威 9

 1 #ifndef SZ_H 2 #define SZ_H 3  4 //只有calc函数对外,可以去掉主函数来当做一个计算模块使用 5 //只要在项目中添加sz、list、fract 6  7 #include <ctype.h> 8 #include "fract.h" 9 10 void calc(char equation[],Fract *ans);11 12 #endif

 

一、知识准备

sz.h

在该程序中输入的数字可以是任意正数、小数。

1+1 = ?

分数计算部分

负数似乎也可以正常运行,即使我没有特意添加检测负数的代码。。。。。

正常来说,我们看到这个表达式都知道怎么运算,知道运算结果

必威 10必威 11

输入的运算符可以是 + - * / ( )

但计算机不一样,计算机无法识别出这串表达式,它只能识别特定的规则:前缀表达式+ 1 1 或后缀表达式1 1 +

  1 #include "fract.h"  2   3 static int commom_divisor(int a,int b);    //最大公约数  4 static int common_multiple(int a,int b);//最小公倍数  5 static void reduce(int *num1,int *num2);    //约分  6   7   8 void Plus(Fract *num1,Fract *num2)  9 { 10     int deno;//公分母 11      12     if(num1->numer==0)    //排除0值计算 13     { 14         *num1=*num2; 15         return; 16     } 17     else if(num2->numer==0) return; 18  19     deno=common_multiple(num1->deno,num2->deno); 20     num1->numer=deno/num1->deno*num1->numer+deno/num2->deno*num2->numer; 21     num1->deno=deno; 22  23 } 24  25 void Minus(Fract *num1,Fract *num2) 26 { 27     num2->numer=-num2->numer; 28     Plus(num1,num2); 29 } 30  31 void Multiply(Fract *num1,Fract *num2) 32 { 33     if(num1->numer==0)return; 34     else if(num2->numer==0) 35     { 36         num1->numer=0; 37         return; 38     } 39  40     reduce(&num1->deno,&num2->numer); 41     reduce(&num1->numer,&num2->deno); 42  43     num1->numer*=num2->numer; 44     num1->deno*=num2->deno; 45  46 } 47  48 void Divide(Fract *num1,Fract *num2) 49 { 50     int temp; 51     if(num2->numer==0) 52     { 53         printf("除数不能为0n"); 54         exit(0); 55     } 56     temp=num2->numer; 57     num2->numer=num2->deno; 58     num2->deno=temp; 59     Multiply(num1,num2); 60 } 61  62  63 static void reduce(int *num1,int *num2)    //约分并保持原来的正负号 64 { 65     int temp,i; 66      67     /*i为0表示都为正,i为1表示num1为正,2表示num2为正,3表示都为负*/ 68     if(*num1<0) 69     { 70         *num1=-*num1; 71         if(*num2<0) 72         { 73             *num2=-*num2; 74             i=3; 75         } 76         else i=2; 77     } 78     else 79         if(*num2<0) 80         { 81             *num2=-*num2; 82             i=1; 83         } 84         else i=0; 85  86     temp=commom_divisor(*num1,*num2); 87     *num1/=temp; 88     *num2/=temp; 89  90     switch 91     { 92         case 0:break; 93         case 1:*num2=-*num2;break; 94         case 2:*num1=-*num1;break; 95         case 3:*num1=-*num1;*num2=-*num2;break; 96     } 97 } 98  99 100 static int commom_divisor(int a,int b)101 {102      int temp,r;103      104     if(a<b)105     {106         temp=a;107         a=b;108         b=temp;109     }110     111     while((r=a%b))112     {113         a=b;114         b=r;115      }116      117     return b;118 }119 120 static int common_multiple(int a,int b)121 {122     return a*b/commom_divisor;123 }

但请确保输入的表达式合法。

举个栗子

fract.c必威 12必威 13

 

(3 + 4) × 5 - 6 就是中缀表达式

 1 #ifndef FRACT_H 2 #define FRACT_H 3  4 #include <stdio.h> 5 #include <stdlib.h> 6  7 //如果有负号则在分子上 8 typedef struct 9 {10     int numer;    //分子11     int deno;    //分母12 }Fract;13 14 //分数的四则运算,结果存在num1中15 void Plus(Fract *num1,Fract *num2);16 void Minus(Fract *num1,Fract *num2);17 void Multiply(Fract *num1,Fract *num2);18 void Divide(Fract *num1,Fract *num2);19 20 #endif

中缀表达式:

形如

9+(3-1)*3+10/2

的数学表达式。特点是运算符在被运算的两个数字中间,也就是我们日常接触的算式。

  • × + 3 4 5 6 前缀表达式
    3 4 + 5 × 6 - 后缀表达式 

fract.h

后缀表达式:

以上面的中缀表达式 9+(3-1)*3+10/2 为例

转换成后缀表达式为 9 3 1-3*+ 10 2/+ 

特点是运算符紧跟在被运算的两个数之后,这样方便程序的理解与计算。

只要顺序读取数字并根据其后的运算符进行相应的操作即可得到结果。

 

对于以上的转换如有不懂可参考

将中缀表达式转化为后缀表达式

 

GitHub地址

所以为了实现程序的自动运算,我们需要将输入的数据转化为前缀或后缀表达式

控制台程序源代码 sz.7z

程序大致分为3步实现:

1)将输入的字符串拆分为数字与运算符,用一个链表储存它们,方便接下来的计算

2)使用仅储存运算符的栈将该中缀表达式转换为后缀表达式

3)使用仅储存数字的栈来运算后缀表达式得到最终答案

 

为实现这3步,代码有点繁琐。。。用了多个文件来分别实现具体功能

以下是各个代码及大概作用,由于比较长,全部折叠了。

前缀、中缀、后缀表达式的概念以及相互转换方法在这里就不多说了,这篇博文 说得比较清楚了

借用如鹏的对话框模版,及上面的计算器部分,实现的图形计算器

Stack.h & Stack.c

实现了一个储存运算符的栈(用于进行第2步)和一个储存数字的栈(用于第3步)

 

必威 14必威 15

 1 //////////////
 2 // Stack.h //
 3 //////////////
 4 
 5 #ifndef _STACK_H_
 6 #define _STACK_H_
 7 
 8 #include<stdlib.h>
 9 
10 #define STACK_INIT_SIZE 10
11 #define STACKINCREMENT 10
12 
13 //优先级的定义
14 #define TopLow -1
15 #define Equal 0
16 #define TopHigh 1
17 //输入的是个括号
18 #define InputIsBrace_1 2
19 #define InputIsBrace_2 3
20 //当前栈顶是个括号
21 #define TopIsBrace 4
22 
23 typedef char SymType;
24 typedef float NumType;
25 
26 //第一步
27 //将中缀表达式转换为后缀表达式
28 //该栈用于储存符号
29 struct _Operator
30 {
31     SymType *Top,*Bottom;
32     int stacksize;
33 };
34 typedef struct _Operator OPERATOR;
35 
36 //新建栈
37 int InitStack_O(OPERATOR *S);
38 
39 //销毁栈
40 int DestroyStack_O(OPERATOR *S);
41 
42 //检测栈是否为空
43 //返回1表示为空
44 int StackEmpty_O(OPERATOR S);
45 
46 //获取栈顶部元素
47 SymType GetTop_O(OPERATOR S);
48 
49 //与栈顶的优先级进行比较
50 int TopIsPriority_O(OPERATOR S, SymType Input,SymType Top);
51 
52 //Push操作,入栈,压栈
53 int Push_O(OPERATOR *S, SymType e);
54 
55 //Pop操作,出栈
56 SymType Pop_O(OPERATOR *S);
57 
58 //以上为符号栈
59 //=====================================================================
60 //以下为数字栈
61 
62 //第二步
63 //计算后缀表达式的值
64 //用于储存数据
65 struct _Number
66 {
67     NumType *Top, *Bottom;
68     int stacksize;
69 };
70 typedef struct _Number NUMBER;
71 
72 //新建栈
73 int InitStack_N(NUMBER *S);
74 
75 //销毁栈
76 int DestroyStack_N(NUMBER *S);
77 
78 //获取栈顶部元素
79 NumType GetTop_N(NUMBER S);
80 
81 //Push操作,入栈,压栈
82 int Push_N(NUMBER *S, NumType e);
83 
84 //Pop操作,出栈
85 NumType Pop_N(NUMBER *S);
86 
87 //接受运算符
88 //取栈顶的两个数字
89 //进行相应运算
90 void DoTheMath(NUMBER*,char);
91 
92 #endif

Stack.h

必威 16必威 17

  1 //////////////
  2 // Stack.c //
  3 /////////////
  4 
  5 #include"Stack.h"
  6 
  7 int InitStack_O(OPERATOR *S)
  8 {
  9     //创建出设定长度的顺序表,地址赋给bottom指针
 10     S->Bottom = (SymType*)malloc(STACK_INIT_SIZE*sizeof(SymType));
 11     if (!S->Bottom)
 12     {
 13         return 0;
 14     }
 15     S->stacksize = STACK_INIT_SIZE;
 16     S->Top = S->Bottom;
 17     return 1;
 18 }
 19 
 20 int DestroyStack_O(OPERATOR *S)
 21 {
 22     S->Top = NULL;
 23     free(S->Bottom);
 24     S->Bottom = NULL;
 25     return 1;
 26 }
 27 
 28 int StackEmpty_O(OPERATOR S)
 29 {
 30     if (S.Bottom == S.Top)
 31     {
 32         return 1;
 33     }
 34     else
 35     {
 36         return 0;
 37     }
 38 }
 39 
 40 SymType GetTop_O(OPERATOR S)
 41 {
 42     if (S.Bottom != S.Top)
 43     {
 44         //由于top指向的是最顶上元素的下一个位置
 45         //所以取出最顶上元素的时候
 46         //要把top减去1
 47         return *(S.Top - 1);
 48     }
 49     return 0;
 50 }
 51 
 52 //与栈顶的优先级进行比较
 53 int TopIsPriority_O(OPERATOR S, SymType Input,SymType top)
 54 {
 55     if (Input == '(')
 56     {
 57         return InputIsBrace_1;
 58     }
 59     if (Input == ')')
 60     {
 61         return InputIsBrace_2;
 62     }
 63     if (top == '(')
 64     {
 65         return TopIsBrace;
 66     }
 67     //-+优先级为1
 68     //*/优先级为2
 69     int p_top, p_input;
 70     if (top == '-' || top == '+')
 71     {
 72         p_top = 1;
 73     }
 74     if (top == '*' || top == '/')
 75     {
 76         p_top = 2;
 77     }
 78     if (Input == '-' || Input == '+')
 79     {
 80         p_input = 1;
 81     }
 82     if (Input == '*' || Input == '/')
 83     {
 84         p_input = 2;
 85     }
 86 
 87     if (p_input > p_top)
 88     {
 89         return TopLow;
 90     }
 91     if (p_input == p_top)
 92     {
 93         return Equal;
 94     }
 95     if (p_input < p_top)
 96     {
 97         return TopHigh;
 98     }
 99     return 0;
100 }
101 
102 int Push_O(OPERATOR *S, SymType e)
103 {
104     //当超出当前栈的容量时进行扩容
105     //这里应该只有等于的情况
106     //而不会大于
107     if ((S->Top - S->Bottom) >= S->stacksize)
108     {
109         //realloc函数将开辟指定大小的储存空间
110         //并将原来的数据全部移到这个新的储存空间
111         S->Bottom = (SymType*)realloc(S->Bottom, (S->stacksize + STACKINCREMENT)*sizeof(SymType));
112         if (!S->Bottom)
113         {
114             return 0;
115         }
116         //由于重新开辟了空间
117         //需要重新根据bottom指针的位置指定top
118         S->Top = S->Bottom + S->stacksize;
119         //最后增加当前栈容量
120         S->stacksize += STACKINCREMENT;
121     }
122     //再把入栈的数据存放好
123     *(S->Top++) = e;
124     return 1;
125 }
126 
127 SymType Pop_O(OPERATOR *S)
128 {
129     if (S->Bottom == S->Top)
130     {
131         return 0;
132     }
133     //top指针先减1再取值
134     return *(--S->Top);
135 }
136 
137 //以上为符号栈的函数
138 //========================================================================
139 //以下为数字栈的函数
140 
141 int InitStack_N(NUMBER *S)
142 {
143     //创建出设定长度的顺序表,地址赋给bottom指针
144     S->Bottom = (NumType*)malloc(STACK_INIT_SIZE*sizeof(NumType));
145     if (!S->Bottom)
146     {
147         return 0;
148     }
149     S->stacksize = STACK_INIT_SIZE;
150     S->Top = S->Bottom;
151     return 1;
152 }
153 
154 int DestroyStack_N(NUMBER *S)
155 {
156     S->Top = NULL;
157     free(S->Bottom);
158     S->Bottom = NULL;
159     return 1;
160 }
161 
162 NumType GetTop_N(NUMBER S)
163 {
164     if (S.Bottom != S.Top)
165     {
166         //由于top指向的是最顶上元素的下一个位置
167         //所以取出最顶上元素的时候
168         //要把top减去1
169         return *(S.Top - 1);
170     }
171     return 0;
172 }
173 
174 int Push_N(NUMBER *S, NumType e)
175 {
176     //当超出当前栈的容量时进行扩容
177     //这里应该只有等于的情况
178     //而不会大于
179     if ((S->Top - S->Bottom) >= S->stacksize)
180     {
181         //realloc函数将开辟指定大小的储存空间
182         //并将原来的数据全部移到这个新的储存空间
183         S->Bottom = (NumType*)realloc(S->Bottom, (S->stacksize + STACKINCREMENT)*sizeof(NumType));
184         if (!S->Bottom)
185         {
186             return 0;
187         }
188         //由于重新开辟了空间
189         //需要重新根据bottom指针的位置指定top
190         S->Top = S->Bottom + S->stacksize;
191         //最后增加当前栈容量
192         S->stacksize += STACKINCREMENT;
193     }
194     //再把入栈的数据存放好
195     *(S->Top++) = e;
196     return 1;
197 }
198 
199 NumType Pop_N(NUMBER * S)
200 {
201     if (S->Bottom == S->Top)
202     {
203         return 0;
204     }
205     //top指针先减1再取值
206     return *(--S->Top);
207 }
208 
209 void DoTheMath(NUMBER *S,char sym)
210 {
211     //从栈顶顺序读入两个数字
212     //进行运算
213     //并将结果压回栈内
214     float num1, num2;
215     num2 = Pop_N(S);
216     num1 = Pop_N(S);
217     switch (sym)
218     {
219     case '+':
220         Push_N(S, num1 + num2);
221         break;
222     case '-':
223         Push_N(S, num1 - num2);
224         break;
225     case '*':
226         Push_N(S, num1*num2);
227         break;
228     case '/':
229         Push_N(S, num1 / num2);
230         break;
231     default:
232         break;
233     }
234 }

Stack.c

所以,在这个计算器的实现中,采用了后缀表达式的实现方式,参考以上文章,重点关注这两个算法:

TAG标签:
版权声明:本文由必威发布于必威-编程,转载请注明出处:学习到栈的作用就好必威:,看看手机中的计算